License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.53
URN: urn:nbn:de:0030-drops-126560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12656/
Schwartz, Roy ;
Sharoni, Yotam
Approximating Requirement Cut via a Configuration LP
Abstract
We consider the {Requirement Cut} problem, where given an undirected graph G = (V,E) equipped with non-negative edge weights c:E → R_{+}, and g groups of vertices X₁,…,X_{g} ⊆ V each equipped with a requirement r_i, the goal is to find a collection of edges F ⊆ E, with total minimum weight, such that once F is removed from G in the resulting graph every X_{i} is broken into at least r_{i} connected components. {Requirement Cut} captures multiple classic cut problems in graphs, e.g., {Multicut}, {Multiway Cut}, {Min k-Cut}, {Steiner k-Cut}, {Steiner Multicut}, and {Multi-Multiway Cut}. Nagarajan and Ravi [Algoritmica`10] presented an approximation of O(log{n}log{R}) for the problem, which was subsequently improved to O(log{g} log{k}) by Gupta, Nagarajan and Ravi [Operations Research Letters`10] (here R = ∑ _{i = 1}^g r_i and k = |∪ _{i = 1}^g X_i |). We present an approximation of O(Xlog{R} √{log{k}}log{log{k}}) for {Requirement Cut} (here X = max _{i = 1,…,g} {|X_i|}). Our approximation in general is incomparable to the above mentioned previous results, however when all groups are not too large, i.e., X = o((√{log{k}}log{g})/(log{R}log{log{k}})), it is better. Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.
BibTeX - Entry
@InProceedings{schwartz_et_al:LIPIcs:2020:12656,
author = {Roy Schwartz and Yotam Sharoni},
title = {{Approximating Requirement Cut via a Configuration LP}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {53:1--53:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12656},
URN = {urn:nbn:de:0030-drops-126560},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.53},
annote = {Keywords: Approximation, Requirement Cut, Sparsest Cut, Metric Embedding}
}
|
Keywords: |
|
Approximation, Requirement Cut, Sparsest Cut, Metric Embedding |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
