Fetching the paper…

Reading the bibliography…

2012

On the practically interesting instances of MAXCUT

Bilu, Yonatan, Daniely, Amit, Linial, Nati et al.

Original
PDF
Post on X

Understand

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.

On the practically interesting instances of MAXCUT · Around

Built on

Eigenvalues and graph bisection: An average case analysis
R. Boppana · 1987
Earlier work this paper cites.
Laplacian eigenvalues and the maximum cut problem
C. Delorme and S. Poljak · 1993
Earlier work this paper cites.
Approximation schemes for dense instances of NP-hard problems
S. Arora, D. Karger, and M. Karpinski · 1995
Earlier work this paper cites.
Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming
M. X. Geomans and D. P. Williamson · 1995
Earlier work this paper cites.
Heuristics for semirandom graph problems
U. Feige and J. Kilian · 1998
Earlier work this paper cites.

Similar

A Randomized Approximation Scheme for Metric MAX-CUT
W. Fernandez de la Vega and Claire Kenyon · 1998
Cited alongside, same era.
Spectral partitioning of random graphs
F. McSherry · 2001
Cited alongside, same era.
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
D. Spielman and S. H. Teng · 2001
Cited alongside, same era.
On Cheeger-type inequalities for weighted graphs
S. Friedland and R. Nabban · 2002
Cited alongside, same era.
A discriminative framework for clustering via similarity functions
M.F. Balcan, A. Blum, and S. Vempala · 2008
Cited alongside, same era.

Then

Which data sets are clusterable? a theoretical study of clusterability
M. Ackerman and S. Ben David · 2009
Later among the works it cites.
Are Stable instances Easy?
Y. Bilu and N. Linial · 2010
Later among the works it cites.
Center-based clustering under perturbation stability
P. Awasthi, A. Blum, and O. Sheffet · 2011
Later among the works it cites.
Clustering under Perturbation Resilience
Original
M. F. Balcan and Y. Liang · 2012
Closest in time.
Clustering is difficult only when it does not matter
A. Daniely, N. Linial, and M. Saks · 2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…