On fixed cost \(k\)-flow problems

DOI10.1007/s00224-014-9572-6zbMath1332.90048OpenAlexW2078521722MaRDI QIDQ260248

Guy Kortsarz, Rohit Khandekar, Zeev Nutov, Mohammad Taghi Hajiaghayi

Publication date: 21 March 2016

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

Full work available at URL: https://doi.org/10.1007/s00224-014-9572-6

zbMATH Keywords

network designapproximation algorithmsfixed cost flowgroup Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (2)

An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized submodular cover problems and applications
• An analysis of the greedy algorithm for the submodular set covering problem
• The minimum shift design problem
• The polymatroid Steiner problems
• A greedy approximation algorithm for the group Steiner problem
• Capacitated Network Design on Undirected Graphs
• On network design problems: fixed cost flows and the covering steiner problem
• Approximability of Capacitated Network Design
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: On fixed cost \(k\)-flow problems