MINIMUM STACKER CRANE PROBLEM

• INSTANCE: Mixed graph $G=\left(V,A,E\right)$, length $l(e)\in N$ for each $e\in A\cup E$ such that for every arc there is a parallel edge of no greater length.

• SOLUTION: A cycle in G (possibly containing repeated vertices) that includes each directed edge in A at least once, traversing such edges only in the specified direction.

• MEASURE: The total length of the cycle.

  
  

• Good News: Approximable within 9/5 [171].

• Garey and Johnson: ND26