Flows on few paths: Algorithms and lower bounds

DOI10.1002/net.20121zbMath1103.90026MaRDI QIDQ5487813

Maren Martens, Martin Skutella

Publication date: 12 September 2006

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20121

zbMATH Keywords

approximation algorithm; network flow; randomized rounding; multicommodity flow; unsplittable flow; \(k\)-splittable flow

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B10: Deterministic network models in operations research

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Flows with Unit Path Capacities and Related Packing and Covering Problems, Comparing branch-and-price algorithms for the multi-commodity \(k\)-splittable maximum flow problem, A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem, An exact approach for the maximum concurrent \(k\)-splittable flow problem, Flows with unit path capacities and related packing and covering problems, A matheuristic approach for the quickest multicommodity \(k\)-splittable flow problem, A local search heuristic for the multi-commodity \(k\)-splittable maximum flow problem, k -Splittable delay constrained routing problem: A branch-and-price approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness of the undirected congestion minimization problem
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New hardness results for congestion minimization and machine scheduling