Some Algorithmic Challenges in Arc Routing
Dipl.-Inf. Manuel Sorge (TU Berlin)
Arc Routing problems occur naturally in many logistic tasks like
delivering mail, garbage disposal, street
sweeping and snow plowing. Such a task is formulated, for example, in the Chinese Postman problem
where, given an edge-weighted graph, one searches for a minimum-weight tour that visits all edges in
the graph. In this simple form, Chinese Postman is solvable in polynomial time, but many variants
that arise in applications yield NP-hard problems. Yet, despite the practical relevance, the literature on
parameterized complexity of Arc Routing problems is rather sparse. We give a brief survey of the known
(parameterized) complexity results and identify some interesting open questions. In particular, we briefly
report on our theoretical and empirical studies related to the Rural Postman problem.
This is joint work with René van Bevern, Rolf Niedermeier, and Mathias Weller.
Back to the research colloquium site.