The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.526
URN: urn:nbn:de:0030-drops-39625
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3962/
Go to the corresponding LIPIcs Volume Portal

Bilu, Yonatan ; Daniely, Amit ; Linial, Nati ; Saks, Michael

On the practically interesting instances of MAXCUT

pdf-format:
50.pdf (0.7 MB)

Abstract

For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances.
Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.

BibTeX - Entry

@InProceedings{bilu_et_al:LIPIcs:2013:3962,
  author =	{Yonatan Bilu and Amit Daniely and Nati Linial and Michael Saks},
  title =	{{On the practically interesting instances of MAXCUT}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{526--537},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3962},
  URN =		{urn:nbn:de:0030-drops-39625},
  doi =		{10.4230/LIPIcs.STACS.2013.526},
  annote =	{Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis}
}

Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI