Semidefinite programs and combinatorial optimization (Q4407449)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1944141
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Semidefinite programs and combinatorial optimization |
scientific article; zbMATH DE number 1944141 |
Statements
2003
0 references
Shannon capacity
0 references
maximum cuts
0 references
discrete linear and quadratic programs
0 references
semidefinite programs
0 references
inference rules
0 references
0.8975517749786377
0 references
0.8891550302505493
0 references
0.8840233683586121
0 references
0.8811874985694885
0 references
0.8648182153701782
0 references
Semidefinite programs and combinatorial optimization (English)
0 references
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].
0 references