Semidefinite programming and combinatorial optimization

被引：18

作者：

Rendl, F ^{[1
]}

机构：

[1] Graz Univ Technol, Inst Math, A-8010 Graz, Austria

来源：

APPLIED NUMERICAL MATHEMATICS | 1999年 / 29卷 / 03期

关键词：

semidefinite programming; integer programs; linear programs over cones; nonlinear relaxations; combinatorial optimization;

D O I：

10.1016/S0168-9274(98)00097-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Semidefinite programs have recently turned out to be a powerful tool for approximating integer problems. To survey the development in this area over the last few years, the following topics are addressed in some detail. First, we investigate ways to derive semidefinite programs from discrete optimization problems. The duality theory for semidefinite programs is the key to understand algorithms to solve them. The relevant duality results are therefore summarized. The second part of the paper deals with the approximation of integer problems both in a theoretical setting, and from a computational point of view. (C) 1999 Elsevier Science B.V. and IMACS, All rights reserved.

引用

页码：255 / 281

页数：27

共 63 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].