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

DOI10.4086/TOC.2017.V013A020zbMATH Open1387.68127arXiv1504.00627OpenAlexW2964263868MaRDI QIDQ4602397FDOQ4602397

Authors: F. Bruce Shepherd, Adrian Vetta 

Publication date: 10 January 2018

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

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

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

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)

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)