Semidefinite programming in combinatorial optimization

被引：0

作者：

Michel X. Goemans

机构：

[1] MIT,Department of Mathematics

来源：

Mathematical Programming | 1997年 / 79卷

关键词：

Semidefinite programming; Combinatorial optimization; Stable set; Maximum cut; Coding theory;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem.

引用

页码：143 / 161

页数：18

共 50 条

[1] Semidefinite programming in combinatorial optimization
Goemans, MX
MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) : 143 - 161
[2] Semidefinite programming and combinatorial optimization
Rendl, F
APPLIED NUMERICAL MATHEMATICS, 1999, 29 (03) : 255 - 281
[3] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION
ALIZADEH, F
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) : 13 - 51
[4] Mixed linear and semidefinite programming for combinatorial and quadratic optimization
Benson, SJ
Ye, YY
Zhang, X
OPTIMIZATION METHODS & SOFTWARE, 1999, 11-2 (1-4) : 515 - 544
[5] Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds
Bertsimas, D
Natarajan, K
Teo, CP
SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) : 185 - 209
[6] Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
Lee, Timothy
Mitchell, John E.
DISCRETE OPTIMIZATION, 2017, 24 : 152 - 169
[7] TRACE OPTIMIZATION USING SEMIDEFINITE PROGRAMMING
Cafuta, Kristijan
Klep, Igor
Povh, Janez
SOR'11 PROCEEDINGS: THE 11TH INTERNATIONAL SYMPOSIUM ON OPERATIONAL RESEARCH IN SLOVENIA, 2011, : 95 - 101
[8] A Semidefinite Programming Approach to Portfolio Optimization
Fonseca, Raquel J.
Wiesemann, Wolfram
Rustem, Berc
21ST EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING, 2011, 29 : 472 - 476
[9] Semidefinite programming
Vandenberghe, L
Boyd, S
SIAM REVIEW, 1996, 38 (01) : 49 - 95
[10] Semidefinite programming relaxations and algebraic optimization in control
Parrilo, PA
Lall, S
EUROPEAN JOURNAL OF CONTROL, 2003, 9 (2-3) : 307 - 321

← 1 2 3 4 5 →