Semidefinite programming in combinatorial optimization

被引：145

作者：

Goemans, MX

机构：

[1] MIT, Department of Mathematics, Cambridge

来源：

MATHEMATICAL PROGRAMMING | 1997年 / 79卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

semidefinite programming; combinatorial optimization; stable set; maximum cut; coding theory;

D O I：

10.1007/BF02614315

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovasz 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. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：143 / 161

页数：19

共 67 条

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