Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-06T22:46:56.019Z 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: yonatan.bilu@mobileye.com)
NATHAN LINIAL
Affiliation:
Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel (e-mail: nati@cs.huji.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

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