Semidefinite programming in combinatorial optimization

DOI10.1007/BF02614315zbMath0887.90139OpenAlexW2085427851WikidataQ98060311 ScholiaQ98060311MaRDI QIDQ1365053

Michel X. Goemans

Publication date: 25 May 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02614315

zbMATH Keywords

semidefinite programmingmaximum cutstable setscoding theoryLovász theta functionstrong valid inequalities

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

On NP-hardness of the clique partition -- independence number gap recognition and related problems, A strong conic quadratic reformulation for machine-job assignment with controllable processing times, Matrix Relaxations in Combinatorial Optimization, Conic mixed-integer rounding cuts, Vertical perimeter versus horizontal perimeter, Unnamed Item, A space decomposition scheme for maximum eigenvalue functions and its applications, A recursive Lovász theta number for simplex-avoiding sets, Sums of Hermitian squares decomposition of non-commutative polynomials in non-symmetric variables using NCSOStools, Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, An unconstrained minimization method for solving low-rank SDP relaxations of the maxcut problem, Dimension reduction for maximum matchings and the fastest mixing Markov chain, Composing and decomposing surfaces and functions, Solving graph equipartition SDPs on an algebraic variety, The Gaussian entropy map in valued fields, Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, Unnamed Item, Interactions of computational complexity theory and mathematics, Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization, Euclidean distortion and the sparsest cut, A globally convergent filter-type trust region method for semidefinite programming, Moment inequalities for sums of random matrices and their applications in optimization, Cardinality constrained minimum cut problems: complexity and algorithms., Vertical versus horizontal Poincaré inequalities on the Heisenberg group, Binary positive semidefinite matrices and associated integer polytopes, A guide to conic optimisation and its applications, A semidefinite programming-based heuristic for graph coloring, On metric properties of maps between Hamming spaces and related graph homomorphisms, Unnamed Item, Fréchet embeddings of negative type metrics, Visualizing network communities with a semi-definite programming method, An axiomatic duality framework for the theta body and related convex corners, Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation, A fast space-decomposition scheme for nonconvex eigenvalue optimization, A probabilistic result for the max-cut problem on random graphs, Semidefinite relaxation for linear programs with equilibrium constraints, Semidefinite programming and combinatorial optimization, Semidefinite programming for discrete optimization and matrix completion problems, Semi-definite relaxation algorithm of multiple knapsack problem, On self-regular IPMs (with comments and rejoinder), Improving an upper bound on the stability number of a graph, Foundations of Set-Semidefinite Optimization, New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction, The omnipresence of Lagrange, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, Semidefinite programming relaxations and algebraic optimization in control, A novel formulation of the max-cut problem and related algorithm, On Minimal Valid Inequalities for Mixed Integer Conic Programs, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, On the connections between semidefinite optimization and vector optimization, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Cuts for mixed 0-1 conic programming, Unnamed Item, A study of search directions in primal-dual interior-point methods for semidefinite programming, SDPLIB 1.2, a library of semidefinite programming test problems, Semidefinite programming, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Optimality conditions for nonsmooth semidefinite programming via convexificators

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Combinatorial properties and the complexity of a max-cut approximation
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Relaxations of vertex packing
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The ellipsoid method and its consequences in combinatorial optimization
• A problem that is easier to solve on the unit-cost algebraic RAM
• Geometric algorithms and combinatorial optimization
• Laplacian eigenvalues and the maximum cut problem
• The sandwich theorem
• Problems of distance geometry and convex properties of quadratic maps
• Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
• Complementarity and nondegeneracy in semidefinite programming
• Connection between semidefinite relaxations of the max-cut and stable set problems
• Approximating the independence number via the \(\vartheta\)-function
• The geometry of graphs and some of its algorithmic applications
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Matrix Analysis
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• On the Shannon capacity of a graph
• A Geometric Approach to Betweenness
• Randomized graph products, chromatic numbers, and Lovasz j-function
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• On the cut polytope
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Semidefinite Programming
• Geometry of cuts and metrics