Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
From MaRDI portal
Publication:4369893
DOI10.1145/227683.227684zbMath0885.68088OpenAlexW1985123706WikidataQ55934039 ScholiaQ55934039MaRDI QIDQ4369893
David P. Williamson, Michel X. Goemans
Publication date: 28 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/227683.227684
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (only showing first 100 items - show all)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation ⋮ Binary vectors for fast distance and similarity estimation ⋮ An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT ⋮ Eigenvalues of Cayley graphs ⋮ Community detection with a subsampled semidefinite program ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Approximation algorithms for two variants of correlation clustering problem ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ Stochastic budget optimization in internet advertising ⋮ Discrete dynamical system approaches for Boolean polynomial optimization ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ A simple method for convex optimization in the oracle model ⋮ Three conjectures in extremal spectral graph theory ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ Solving rank-constrained semidefinite programs in exact arithmetic ⋮ An exact semidefinite programming approach for the max-mean dispersion problem ⋮ A class of spectral bounds for max \(k\)-cut ⋮ Inapproximability ratios for crossing number ⋮ Theorems of the alternative for conic integer programming ⋮ Tighter spectral bounds for the cut size, based on Laplacian eigenvectors ⋮ A new approximation hierarchy for polynomial conic optimization ⋮ The geometry of SDP-exactness in quadratic optimization ⋮ Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ On lazy bureaucrat scheduling with common deadlines ⋮ Submodular optimization problems and greedy strategies: a survey ⋮ A representation theory perspective on simultaneous alignment and classification ⋮ Drawing (complete) binary tanglegrams ⋮ Convolutional neural network learning for generic data classification ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ The maximum cut problem on blow-ups of multiprojective spaces ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Improved semidefinite bounding procedure for solving max-cut problems to optimality ⋮ Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems ⋮ Cuts in undirected graphs. I ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ Additive approximation algorithms for modularity maximization ⋮ On the efficiency of influence-and-exploit strategies for revenue maximization under positive externalities ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Computational protein design as an optimization problem ⋮ Approximation algorithms for maximum cut with limited unbalance ⋮ Approximating the fixed linear crossing number ⋮ On a polynomial fractional formulation for independence number of a graph ⋮ \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation ⋮ A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion ⋮ Exact MAX-2SAT solution via lift-and-project closure ⋮ On the asymptotic minimum number of monochromatic 3-term arithmetic progressions ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ Round robin scheduling -- a survey ⋮ Dimension reduction by random hyperplane tessellations ⋮ A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ Exploiting semidefinite relaxations in constraint programming ⋮ A multiple penalty function method for solving max-bisection problems ⋮ Exploring the relationship between max-cut and stable set relaxations ⋮ Lagrangian smoothing heuristics for Max-cut ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Robust global optimization with polynomials ⋮ Approximation algorithms for the bi-criteria weighted MAX-CUT problem ⋮ Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming ⋮ Frequency-hopping code design for Target detection via optimization theory ⋮ A semidefinite programming based polyhedral cut and price approach for the maxcut problem ⋮ Lower bound improvement and forcing rule for quadratic binary programming ⋮ Semidefinite programming relaxations and algebraic optimization in control ⋮ A novel formulation of the max-cut problem and related algorithm ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ An evaluation of semidefinite programming based approaches for discrete lot-sizing problems ⋮ Phase recovery, MaxCut and complex semidefinite programming ⋮ Phase retrieval from coded diffraction patterns ⋮ Barvinok's naive algorithm in distance geometry ⋮ Approximating max-cut under graph-MSO constraints ⋮ A simple algorithm for the multiway cut problem ⋮ Some observations on the smallest adjacency eigenvalue of a graph ⋮ Volume computation for sparse Boolean quadric relaxations ⋮ Conic relaxation approaches for equal deployment problems ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Theory versus practice in annealing-based quantum computing ⋮ Solution of Boolean quadratic programming problems by two augmented Lagrangian algorithms based on a continuous relaxation ⋮ Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting ⋮ Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem ⋮ On fractional cut covers ⋮ Exact recovery in the Ising blockmodel ⋮ Immediate schedule adjustment and semidefinite relaxation ⋮ A max-cut approach to heterogeneity in cryo-electron microscopy ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ Hypergraph cuts above the average ⋮ Sharing hash codes for multiple purposes ⋮ A semidefinite optimization approach for the single-row layout problem with unequal dimensions ⋮ Efficient algorithms for online decision problems ⋮ Cuts for mixed 0-1 conic programming ⋮ Oblivious algorithms for the maximum directed cut problem ⋮ Robust computation of linear models by convex relaxation ⋮ Speeding up a memetic algorithm for the max-bisection problem ⋮ An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
Uses Software
This page was built for publication: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
