direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Date
Speaker
Location
Language
30.05.2013 16:15
Manuel Sorge
TEL 512
english/german

Back to the research colloquium site.

Zusatzinformationen / Extras