Max Cut and the Smallest Eigenvalue

Eigenvalue techniques in design and graph theory

Willem Haemers · 1979

Earlier work this paper cites.

Eigenvalues and expanders

Noga Alon · 1986

Earlier work this paper cites.

Simple constructions of almost k k -wise independent random variables

N. Alon, O. Goldreich, J. Håstad, and R. Peralta · 1992

Earlier work this paper cites.

Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start

J. Kuczynski and H. Wozniakowski · 1992

Earlier work this paper cites.

Combinatorial properties and the complexity of a max-cut approximation

Charles Delorme and Svatopluk Poljak · 1993

Earlier work this paper cites.

Laplacian eigenvalues and the maximum cut problem

Charles Delorme and Svatopluk Poljak · 1993

Earlier work this paper cites.

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Michel X. Goemans and David P. Williamson · 1995

Earlier work this paper cites.

Bipartite subgraphs and the smallest eigenvalue

Noga Alon and Benny Sudakov · 2000

Earlier work this paper cites.

Non-approximability results for optimization problems on bounded degree instances

Luca Trevisan · 2001

Earlier work this paper cites.

On the power of unique 2-prover 1-round games

Subhash Khot · 2002

Earlier work this paper cites.

Semidefinite programs and combinatorial optimization

Laszlo Lovász · 2003

Cited alongside, same era.

Expander flows and a log ⁡ n \sqrt{\log n} -approximation to sparsest cut

Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2004

Cited alongside, same era.

Maximizing quadratic programs: Extending Grothendieck’s inequality

Moses Charikar and Anthony Wirth · 2004

Cited alongside, same era.

Optimal inapproximability results for MAX-CUT and other two-variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2004

Cited alongside, same era.

Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Daniel Spielman and Shang-Hua Teng · 2004

Cited alongside, same era.

O ⁡ ( log ⁡ n ) O(\sqrt{\log n}) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

SDP gaps and UGC-hardness for MAXCUTGAIN

Subhash Khot and Ryan O’Donnell · 2006

Later among the works it cites.

Graph partitioning using single commodity flows

Rohit Khandekar, Satish Rao, and Umesh V. Vazirani · 2006

Later among the works it cites.

A combinatorial, primal-dual approach to semidefinite programs

Sanjeev Arora and Satyen Kale · 2007

Later among the works it cites.

The spectral radius and the maximum degree of irregular graphs

Sebastian M. Cioaba · 2007

Later among the works it cites.

Linear programming relaxations of maxcut

Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu · 2007

Later among the works it cites.

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani · 2007

Later among the works it cites.