direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2008

Flows with Unit Path Capacities and Related Packing and Covering Problems
Zitatschlüssel Report-021-2008
Autor Maren Martens and Martin Skutella
Jahr 2008
Nummer 021
Notiz To appear in B. Yang, D.-Z. Du, and C. A. Wang (eds.): Combinatorial Optimization and Applications, Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA'08), Lecture Notes in Computer Science 5165, Springer-Verlag: Berlin, 2008, 180-189.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum $s$-$t$-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the $k$ shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting $O(łog m)$-approximation algorithm, where $m$ is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrtm)$-approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag