Approximation Algorithms for Single-Source Unsplittable Flow

DOI10.1137/S0097539799355314zbMath1017.68058OpenAlexW1994772417MaRDI QIDQ2784488

Stavros G. Kolliopoulos, Clifford Stein

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799355314

zbMATH Keywords

parallel machine schedulingapproximation algorithmsnetwork algorithmsnetwork flowroutingdisjoint pathsunsplittable flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Related Items (13)

Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ Approximations for generalized unsplittable flow on paths with application to power systems optimization ⋮ Maximizing throughput in queueing networks with limited flexibility ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ On the minimum cost multiple-source unsplittable flow problem ⋮ Computing Nash equilibria for scheduling on restricted parallel links ⋮ The Influence of Link Restrictions on (Random) Selfish Routing ⋮ Single-source \(k\)-splittable min-cost flows ⋮ Minimum-cost single-source 2-splittable flow ⋮ Minimum-Cost Single-Source 2-Splittable Flow ⋮ Single source unsplittable flows with arc-wise lower and upper bounds

This page was built for publication: Approximation Algorithms for Single-Source Unsplittable Flow