TY - GEN

T1 - Submodular cost allocation problem and applications

AU - Chekuri, Chandra

AU - Ene, Alina

PY - 2011

Y1 - 2011

N2 - We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set V and k non-negative submodular set functions f 1,....,f k on V. The objective is to partition V into k (possibly empty) sets A 1,⋯, A k such that the sum ∑i=1 k f i (A i ) is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lovász-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for related problems. In particular, we give a (1.5 - 1/k)-approximation for the hypergraph multiway partition problem. We also give a min {2(1 - 1/k), H Δ}- approximation for the hypergraph multiway cut problem when Δ is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.

AB - We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set V and k non-negative submodular set functions f 1,....,f k on V. The objective is to partition V into k (possibly empty) sets A 1,⋯, A k such that the sum ∑i=1 k f i (A i ) is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lovász-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for related problems. In particular, we give a (1.5 - 1/k)-approximation for the hypergraph multiway partition problem. We also give a min {2(1 - 1/k), H Δ}- approximation for the hypergraph multiway cut problem when Δ is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.

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

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

U2 - 10.1007/978-3-642-22006-7_30

DO - 10.1007/978-3-642-22006-7_30

M3 - Conference contribution

AN - SCOPUS:79959998988

SN - 9783642220050

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 354

EP - 366

BT - Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings

T2 - 38th International Colloquium on Automata, Languages and Programming, ICALP 2011

Y2 - 4 July 2011 through 8 July 2011

ER -