Are Stable Instances Easy?
We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP–hard problems are easier to solve. In particular, whether there exist algorithms that solve correctly and in polynomial time all sufficiently stable instances of some NP–hard problem. The paper focuses on the Max–Cut problem, for which we show that this is indeed the case.
complexity max cut average case complexity expander graphs stability
Yonatan Bilu Nathan Linial
Mobileye Vision Technologies Ltd., 13 Hartom Street, PO Box 45157, Jerusalem, 91450 Israel Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel
国际会议
The First Symposium on Innovations in Computer Science(2010 计算机科学创新研讨会 ICS 2010)
北京
英文
332-341
2010-01-05（万方平台首次上网日期，不代表论文的发表时间）