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 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

      Identifiers