TY - JOUR

T1 - On Fixed Cost k-Flow Problems

AU - Hajiaghayi, Mohammad Taghi

AU - Khandekar, Rohit

AU - Kortsarz, Guy

AU - Nutov, Zeev

N1 - Funding Information:
Part of this work was done at DIMACS. We thank DIMACS for their hospitality. A preliminary version appeared in archive [] in 2011. Supported in part by NSF CAREER award 1053605, ONR YIP award N000141110662, DARPA/AFRL award FA8650-11-1-7162, and University of Maryland Research and Scholarship Award (RASA). The author is also with AT&T Labs– Research, Florham Park, NJ. Supported in part by NSF grant number 434923.
Publisher Copyright:
© 2014, Springer Science+Business Media New York.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {ue∣e ∈ E} and edge-costs {ce∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an (Formula Presented) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {bv : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log3+∈n approximation scheme for it using Group Steiner Tree techniques.

AB - In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {ue∣e ∈ E} and edge-costs {ce∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an (Formula Presented) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {bv : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log3+∈n approximation scheme for it using Group Steiner Tree techniques.

KW - Approximation algorithms

KW - Fixed cost flow

KW - Group Steiner tree

KW - Network design

UR - http://www.scopus.com/inward/record.url?scp=84952950970&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84952950970&partnerID=8YFLogxK

U2 - 10.1007/s00224-014-9572-6

DO - 10.1007/s00224-014-9572-6

M3 - Article

AN - SCOPUS:84952950970

SN - 1432-4350

VL - 58

SP - 4

EP - 18

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -