License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.7
URN: urn:nbn:de:0030-drops-100335
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10033/
Chekuri, Chandra ;
Quanrud, Kent ;
Xu, Chao
LP Relaxation and Tree Packing for Minimum k-cuts
Abstract
Karger used spanning tree packings [Karger, 2000] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm [Karger, 1995; Karger and Stein, 1996]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [Thorup, 2008].
In this paper we revisit properties of an LP relaxation for k-cut proposed by Naor and Rabani [Naor and Rabani, 2001], and analyzed in [Chekuri et al., 2006]. We show that the dual of the LP yields a tree packing, that when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Karger's analysis for mincut to the k-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorup's algorithm by a factor of n. We also improve the bound on the number of alpha-approximate k-cuts. Second, we give a simple proof that the integrality gap of the LP is 2(1-1/n). Third, we show that an optimum solution to the LP relaxation, for all values of k, is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of Barahona [Barahona, 2000] and Ravi and Sinha [Ravi and Sinha, 2008]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP. This work arose from an effort to understand and simplify the results of Thorup [Thorup, 2008].
BibTeX - Entry
@InProceedings{chekuri_et_al:OASIcs:2018:10033,
author = {Chandra Chekuri and Kent Quanrud and Chao Xu},
title = {{LP Relaxation and Tree Packing for Minimum k-cuts}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {7:1--7:18},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-099-6},
ISSN = {2190-6807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10033},
URN = {urn:nbn:de:0030-drops-100335},
doi = {10.4230/OASIcs.SOSA.2019.7},
annote = {Keywords: k-cut, LP relaxation, tree packing}
}
|
Keywords: |
|
k-cut, LP relaxation, tree packing |
|
Collection: |
|
2nd Symposium on Simplicity in Algorithms (SOSA 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
