Semidefinite programs and combinatorial optimization
The author surveys semidefinite optimization mainly as relaxation of discrete optimization problems. He starts with two examples, a proof and an approximation algorithm, where semidefinite optimization plays an important role. Still among the preliminaries, the author surveys some areas which play a role in semidefinite optimization: linear algebra, linear programming, and polyhedral combinatorics. After introducing semidefinite programs and discussing some of their basic properties, he shows that semidefinite programs arise in a variety of ways: as certain geometric extremal problems, as relaxation of combinatorial optimization problems, in optimizing eigenvalue bounds in graph theory, as stability problems in engineering. Next, he shows through examples from graph theory, number theory, and logic how semidefinite optimization can be used in proofs as well in the design of approximation algorithms. In Chapter 6.7 the authors tries to put the combinatorial applications of semidefinite optimization in a broader perspective. Several roadblocks are described in Chapter 6.8. For the entire collection see [Zbl 1005.00014].
- Semidefinite programming and combinatorial optimization
- Semidefinite programming in combinatorial and polynomial optimization
- Semidefinite programming and integer programming
- Semidefinite programming in combinatorial optimization
- Polyhedral and semidefinite programming methods in combinatorial optimization
- An object-oriented approach to semidefinite programming
- On the complexity of semidefinite programs
- Semidefinite programming in combinatorial optimization
- Complementarity and nondegeneracy in semidefinite programming
- Gray code enumeration of families of integer partitions
- Ideals of graph homomorphisms
- Generating valid linear inequalities for nonlinear programs via sums of squares
- Optimality conditions and global convergence for nonlinear semidefinite programming
- On the linear classification of even and odd permutation matrices and the complexity of computing the permanent
- Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
- Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
- Maximum algebraic connectivity augmentation is NP-hard
- Semidefinite programming based approaches to the break minimization problem
- Approximating projections by quantum operations
- Integer sequences and semidefinite programming
- Exponential lower bounds for polytopes in combinatorial optimization
- Convex hulls of algebraic sets
- Convex relaxations and integrality gaps
- Relaxations of combinatorial problems via association schemes
- Two-level polytopes with a prescribed facet
- Max k-cut and the smallest eigenvalue
- Semidefinite programming in combinatorial and polynomial optimization
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Matrix relaxations in combinatorial optimization
- scientific article; zbMATH DE number 6000615 (Why is no real title available?)
- scientific article; zbMATH DE number 4001882 (Why is no real title available?)
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- scientific article; zbMATH DE number 1489798 (Why is no real title available?)
- Cutting planes for mixed 0-1 semidefinite programs
- Prestress stability of triangulated convex polytopes and universal second-order rigidity
- A guide to conic optimisation and its applications
- SOS is not obviously automatizable, even approximately
- On Farkas lemma and dimensional rigidity of bar frameworks
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Semidefinite programming and integer programming
- Undecidability of linear inequalities in graph homomorphism densities
- The entropy rounding method in approximation algorithms
- Semidefinite programming and combinatorial optimization
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Empirical Properties of Optima in Free Semidefinite Programs
- Negativizability: a useful property for distributed state estimation and control in cyber-physical systems
- scientific article; zbMATH DE number 7692356 (Why is no real title available?)
- Polyhedral and semidefinite programming methods in combinatorial optimization
- A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
- Convex hulls of curves of genus one
- Beyond the Existential Theory of the Reals
- Relaxations and cutting planes for linear programs with complementarity constraints
- Real Schur norms and Hadamard matrices
- A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem
- An index for inclusions of operator systems
- Semidefinite programming for discrete optimization and matrix completion problems
- Distributed state estimation for interdependent and switching multi-agent systems
- Safely learning dynamical systems
- Complexity classification of product state problems for local Hamiltonians
- Computer-assisted design of accelerated composite optimization methods: OptISTA
- Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
- Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited
This page was built for publication: Semidefinite programs and combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4407449)
