MINIMUM K-STACKER CRANE PROBLEM

Next: MINIMUM GENERAL ROUTING Up: Routing Problems Previous: MINIMUM STACKER CRANE PROBLEM Index

INSTANCE: Mixed graph $G=\left(V,A,E\right)$ , initial vertex $s\in V$ , length $l(e)\in N$ for each $e\in A\cup E$ ,
SOLUTION: A collection of k cycles, each containing the initial vertex s, that collectively traverse each directed edge in A at least once.
MEASURE: The maximum length of the k cycles.
Good News: Approximable within 14/5-1/k [171].

Viggo Kann
2000-03-20