1 Search Results for "Sharoni, Yotam"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.53
Approximating Requirement Cut via a Configuration LP

Authors: Roy Schwartz and Yotam Sharoni

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.
Cite as

Roy Schwartz and Yotam Sharoni. Approximating Requirement Cut via a Configuration LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.APPROX/RANDOM.2020.53,
  author =	{Schwartz, Roy and Sharoni, Yotam},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.53},
  URN =		{urn:nbn:de:0030-drops-126560},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.53},
  annote =	{Keywords: Approximation, Requirement Cut, Sparsest Cut, Metric Embedding}
}
  • Refine by Author
  • 1 Schwartz, Roy
  • 1 Sharoni, Yotam

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Approximation
  • 1 Metric Embedding
  • 1 Requirement Cut
  • 1 Sparsest Cut

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact