Semidefinite programming in combinatorial optimization

Data:	1997
Resum:	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. .
Drets:	Tots els drets reservats.
Llengua:	Anglès
Document:	Article ; recerca ; Versió publicada
Matèria:	Semidefinite programming ; Combinatorial optimization ; Stable set ; Maximum cut ; Coding theory
Publicat a:	Mathematical Programming, vol. 79 n. 1-3 (1997) p. 143-161, ISSN 0025-5610

19 p, 1.1 MB

Accés restringit a la UAB

Registre creat el 2006-03-13, darrera modificació el 2023-06-03