2026-07-22T20:50:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3962 2024-03-06T10:34:43Z ddc:004 open_access

On the practically interesting instances of MAXCUT Bilu, Yonatan Daniely, Amit Linial, Nati Saks, Michael MAXCUT Clustering Hardness in practice Stability Non worst-case analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yonatan Bilu and Amit Daniely and Nati Linial and Michael Saks 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.526 urn:nbn:de:0030-drops-39625 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.526 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode