On the practically interesting instances of MAXCUT
On the practically interesting instances of MAXCUT
复制标题
关于 MAXCUT 的实际有趣实例
DOI：
10.4230/lipics.stacs.2013.526
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
M. Saks
中科院分区：
文献类型：
--
作者：
Yonatan Bilu;Amit Daniely;N. Linial;M. Saks
传统上，根据其最坏情况的硬度来量化计算问题的复杂性。这种方法具有许多优势，并导致了深刻而美丽的理论。但是，从实际的角度来看，这还有很多不足之处。在应用领域，实际上有趣的实例经常仅占据算法的实例空间的很小一部分，并且绝大多数实例简直是无关紧要的。解决这些问题是理论计算机科学的主要挑战，这可能使理论与计算机科学实践更相关。
在Bilu和Linial之后，我们将此视角应用于Maxcut，被视为聚类问题。使用各种技术，我们研究了这个问题的实际情况。具体而言，我们展示了如何在轻度稳定性假设下的多项式时间内求解，度量，扩展和密集的实例。特别是，$（1+ \ epsilon）$ - 稳定性（最佳）足以满足度量和密集的麦克图。我们还展示了如何在多项式时间$ \ omega（\ sqrt {n}）$ - Maxcut的稳定实例中解决，从而大大改善了最佳以前已知的结果。
The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful theory. However, from the practical perspective, this leaves much to be desired. In application areas, practically interesting instances very often occupy just a tiny part of an algorithm's space of instances, and the vast majority of instances are simply irrelevant. Addressing these issues is a major challenge for theoretical computer science which may make theory more relevant to the practice of computer science.
Following Bilu and Linial, 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.