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

By Michel X. Goemans, David P. Williamson. 1995

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “, sign random projections (SRP) [10, 3]) or 2-bit coding are often better compared to using more bits.”
Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “A randomized, non-greedy algorithm, referred to as SDP, is also implemented based on [12]; 100 solutions are generated for each graph, and the best one is taken.”
Certified Defenses against Adversarial Examples (2018, background): “While MAXCUT is NP-hard, it can be efficiently approximated, as shown by the celebrated semidefinite programming relaxation for MAXCUT in Goemans & Williamson (1995).”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, methodology): “Other than generalizing combinatorial optimization problems like Max Cut [19], Max Directed Cut [4, 22], hypergraph cut problems, maximum facility location [2, 9, 10], and certain restricted satisfiability problems [25, 14], maximizing non-monotone submodular functions have applications in a variety”
Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (2009, methodology): “Apply the Goemans-Williamson hyperplane rounding technique [23] to the primal matrix X obtained from solving the SDP during the bundle iterations.”
Pseudo-Boolean optimization (2002, methodology): “[5, 69, 70]), and the above simple rounding procedures are special cases of the “probabilistic rounding” technique based on conditional probabilities, introduced in [37, 142, 143].”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, unknown): “We exhibit the first provably correct algorithm for these problems with optimal storage.”
Geometric representations of graphs (2014, result): “The ordering of the nodes which approximates the bandwidth is now obtained through a random projection of the representation to the line, in a fashion similar to the Goemans–Williamson algorithm above.”
Online Submodular Maximization with Preemption (2015, background): “Bar-Noy and Lampis [6] gave a (1 / 3)-competitive deterministic algorithm for an online model of Max-Cut where every revealed node is accompanied by its input and output degrees.”
Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search (2013, methodology): “For example, [26] directly used the bits from b-bit minwise hashing [20, 23] to build hash tables and demonstrated the significant advantages compared to sim-hash [8, 12] and spectral hashing [29].”
Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors (2011, background): “This robustness property enables us to upper bound the reconstruction performance even when some measurement signs have been changed due to noise.”
Relaxations of Quadratic Programs in Operator Theory and System Analysis (2001, methodology): “it was shown in [2] that (15) holds with a better constant c ≈ 0.”
A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization (2003, methodology): “For the full details on the maxcut SDP relaxation, we refer the reader to [13].”
Optimal a priori balance in the design of controlled experiments (2013, background): “+ : diag(P ) = e, Pe = 0 and is motivated by [44] and [45].”
Introducing SOSTOOLS: a general purpose sum of squares programming solver (2002, background): “In relation to this, it can be noted that the SDP relaxation of Goemans and Williamson [3] is a special case”