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 (60)

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

This page was built for publication: Semidefinite programming in combinatorial optimization