Approximation algorithms for single-source unsplittable flow

DOI10.1137/S0097539799355314MaRDI QIDQ2784488zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsdisjoint pathsnetwork algorithmsnetwork flowparallel machine schedulingroutingunsplittable flow

Mathematics Subject Classification ID

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

Recommendations

• On the single-source unsplittable flow problem
• The \(k\)-splittable flow problem
• Approximating the single source unsplittable min-cost flow problem
• scientific article; zbMATH DE number 1947385
• scientific article; zbMATH DE number 1947047

Cited in

(31)

• Single-source \(k\)-splittable min-cost flows
• A note on the greedy algorithm for the unsplittable flow problem
• Minimum-cost single-source 2-splittable flow
• On the single-source unsplittable flow problem
• Approximating covering integer programs with multiplicity constraints
• Approximating the single source unsplittable min-cost flow problem
• Single source unsplittable flows with arc-wise lower and upper bounds
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A polynomial time approximation algorithm for the two-commodity splittable flow problem
• Maximizing throughput in queueing networks with limited flexibility
• NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
• Meet and merge: approximation algorithms for confluent flows
• Approximations for generalized unsplittable flow on paths with application to power systems optimization
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• On the minimum cost multiple-source unsplittable flow problem
• Approximability of unsplittable shortest path routing problems
• Minimum-Cost Single-Source 2-Splittable Flow
• Implementing approximation algorithms for the single-source unsplittable flow problem
• Convex Combinations of Single Source Unsplittable Flows
• On the Approximability of the Minimum Congestion Unsplittable Shortest Path Routing Problem
• New Algorithms for the Unsplittable Flow Problem
• scientific article; zbMATH DE number 1342140 (Why is no real title available?)
• scientific article; zbMATH DE number 1947047 (Why is no real title available?)
• The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
• Single source unsplittable flows with arc-wise lower and upper bounds
• The Influence of Link Restrictions on (Random) Selfish Routing
• Computing Nash equilibria for scheduling on restricted parallel links
• An enhanced Benders decomposition method for unique shortest path routing
• Integer and unsplittable multiflows in series-parallel digraphs
• Approximation algorithms for the unsplittable flow problem

This page was built for publication: Approximation algorithms for single-source unsplittable flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784488)