Semidefinite programming in combinatorial optimization
type: Item
instance of: scholarly article
title: Semidefinite programming in combinatorial optimization
zbMATH Open document ID: 0887.90139
DOI: 10.1007/BF02614315
author: Michel X. Goemans
published in: Mathematical Programming. Series A. Series B
publication date: 1998-05-25T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 1053956
zbMATH Keywords: coding theory
zbMATH Keywords: stable sets
zbMATH Keywords: semidefinite programming
zbMATH Keywords: Lovász theta function
zbMATH Keywords: strong valid inequalities
zbMATH Keywords: maximum cut
MaRDI profile type: Publication
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: Complementarity and nondegeneracy in semidefinite programming
cites work: Eigenvalues and expanders
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: On the cut polytope
cites work: Problems of distance geometry and convex properties of quadratic maps
cites work: On Lipschitz embedding of finite metric spaces in Hilbert space
cites work: Q4871763
cites work: A Geometric Approach to Betweenness
cites work: Combinatorial properties and the complexity of a max-cut approximation
cites work: Laplacian eigenvalues and the maximum cut problem
cites work: Q5707657
cites work: Geometry of cuts and metrics
cites work: Randomized graph products, chromatic numbers, and Lovasz j-function
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Q3328583
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Relaxations of vertex packing
cites work: Geometric algorithms and combinatorial optimization
cites work: Q4526964
cites work: Approximation Algorithms for the Set Covering and Vertex Cover Problems
cites work: Matrix Analysis
cites work: Approximate graph coloring by semidefinite programming
cites work: Q4228497
cites work: The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
cites work: The sandwich theorem
cites work: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
cites work: Q3222981
cites work: Connection between semidefinite relaxations of the max-cut and stable set problems
cites work: Q5690370
cites work: The geometry of graphs and some of its algorithmic applications
cites work: On the Shannon capacity of a graph
cites work: Q3320435
cites work: Q3973406
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Q4146667
cites work: Q4231921
cites work: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
cites work: Q4281312
cites work: Q4324980
cites work: Q3137209
cites work: Nonpolyhedral Relaxations of Graph-Bisection Problems
cites work: Q4840774
cites work: A comparison of the Delsarte and Lovász bounds
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Approximate counting, uniform generation and rapidly mixing Markov chains
cites work: A problem that is easier to solve on the unit-cost algebraic RAM
cites work: Semidefinite Programming
Wikidata QID: Q98060311
full work available at URL: https://doi.org/10.1007/bf02614315
OpenAlex ID: W2085427851
description: scientific article; zbMATH DE number 1053956