Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2000/603/

Helmberg, Christoph

Semidefinite Programming for Combinatorial Optimization

pdf-Format:
Dokument 1.pdf (11.714 KB)
ps-Format:
Dokument 1.ps (1.840 KB)

Kurzfassung in Englisch

This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods.
We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation.
In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming.
One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.

Freie Schlagwörter (englisch): positive semidefinite matrices , semidefinite cone , semidefinite Programming , semidefinite duality , combinatorial optimization , max-cut , quadrati
MSC - Klassifikation 90-02
MSC - Klassifikation 90C27
MSC - Klassifikation 90C22
Abteilung: ZIB Allgemein
DDC-Sachgruppe: Allgemeines, Wissenschaft
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 00-34
Quelle: no further publication planned / keine weitere Veröffentlichung vorgesehen
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 10.10.2000

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: