Flows on few paths: Algorithms and lower bounds

DOI10.1002/net.20121zbMath1103.90026OpenAlexW1515075899MaRDI 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 algorithmnetwork flowrandomized roundingmulticommodity flowunsplittable flow\(k\)-splittable flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

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

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

This page was built for publication: Flows on few paths: Algorithms and lower bounds