Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-02T04:03:47.909Z Has data issue: false hasContentIssue false
  • English
  • Français

Are Stable Instances Easy?

Published online by Cambridge University Press:  26 July 2012

YONATAN BILU  and
NATHAN LINIAL
YONATAN BILU
Affiliation:
Mobileye Vision Technologies Ltd, 13 Hartom Street, PO Box 45157, Jerusalem, 91450Israel (e-mail: [email protected])
NATHAN LINIAL
Affiliation:
Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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, and in particular, whether there exist algorithms that solve 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.

Keywords

Primary 68Q17Secondary 05C50
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 643 - 660
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ackerman, M. and Ben David, S. (2009) Clusterability, A theoretical study. Proc. 12th International Conference on Artificial Intelligence and Statistics, Vol. 5, pp. 1–8.Google Scholar
[2]Balcan, M. F., Blum, A. and Gupta, A. (2009) Approximate clustering without the approximation. In SODA '09: Proc. Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 1068–1077.Google Scholar
[3]Bilu, Y. On spectral properties of graphs and their application to clustering. PhD Thesis, available at http://www.cs.huji.ac.il/~nati/PAPERS/THESIS/bilu.pdf.Google Scholar
[4]Boppana, R. (1987) Eigenvalues and graph bisection: An average case analysis. In 28th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 280–285.Google Scholar
[5]Bui, T. N.Chaudhuri, S., Leighton, F. T. and Sipser, M. (1987) Graph bisection algorithms with good average case behavior. Combinatorica 7 171–191.CrossRefGoogle Scholar
[6]Condon, A. and Karp, R. M. (2001) Algorithms for graph partitioning on the planted partition model. Random Struct. Alg. 18 116–140.Google Scholar
[7]Delorme, C. and Poljak, S. (1993) Laplacian eigenvalues and the maximum cut problem. Math. Programming 62 557–574.CrossRefGoogle Scholar
[8]Dyer, M. E. and Frieze, A. (1986) Fast solution of some random NP-hard problems. In 27th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 313–321.Google Scholar
[9]Feige, U. and Kilian, J. (2001) Heuristics for semirandom graph problems. J. Comput. System Sci. 63 639–671.CrossRefGoogle Scholar
[10]Goemans, M. X. and Williamson, D. P. (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 1115–1145.CrossRefGoogle Scholar
[11]Grötschel, M., Lovász, L. and Schrijver, A. (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 169–197.Google Scholar
[12]Grötschel, M., Lovász, L. and Schrijver, A. (1984) Corrigendum to our paper: ‘The ellipsoid method and its consequences in combinatorial optimization’ [Combinatorica 1 (1981) 169–197]. Combinatorica 4 291–295.CrossRefGoogle Scholar
[13]Jerrum, M. and Sorkin, G. B. (1998) The Metropolis algorithm for graph bisection. Discrete Appl. Math. 82 155–175.CrossRefGoogle Scholar
[14]McSherry, F. (2001) Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 529–537.CrossRefGoogle Scholar
[15]Mohar, B. (1989) Isoperimetric numbers of graphs. J. Combin. Theory Ser. B 291 47–274.Google Scholar
[16]Ostrovsky, R., Rabani, Y., Schulman, L. J. and Swamy, C. (2006) The effectiveness of Lloyd-type methods for the k-means problem. In FOCS '06: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 165–176.Google Scholar
[17]Papadimitriou, C. H. (1994) Computational Complexity, Addison-Wesley.Google Scholar
[18]Shamir, R. and Tsur, D. (2002) Improved algorithms for the random cluster graph model. In Proc. 8th Scandinavian Workshop on Algorithm Theory, pp. 230–239.CrossRefGoogle Scholar
[19]Spielman, D. and Teng, S. H. (2001) Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In Proc. 33rd Annual ACM Symposium on Theory of Computing, ACM Press, pp. 296–305.Google Scholar
[20]Vershynin, R. (2006) Beyond Hirsch conjecture: Walks on random polytopes and smoothed complexity of the simplex method. In FOCS '06: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 133–142.Google Scholar