The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems

DOI10.4086/TOC.2017.V013A020MaRDI QIDQ4602397zbMATH OpenOpenAlexFDO

Authors F. Bruce Shepherd, Adrian Vetta

Publication date 10 January 2018

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1504.00627

zbMATH Keywords

algorithmscomplexity theorynetwork flowunsplittable flowmultiflowconfluent flowpriority flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the single-source unsplittable flow problem
• scientific article; zbMATH DE number 1947047
• Approximation algorithms for single-source unsplittable flow
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows

Cited in

(4)

• Minmax regret for sink location on dynamic flow paths with general capacities
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

This page was built for publication: The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems

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