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 条
  • [31] A note on semidefinite programming relaxations for polynomial optimization over a single sphere
    HU Jiang
    JIANG Bo
    LIU Xin
    WEN ZaiWen
    Science China(Mathematics), 2016, 59 (08) : 1543 - 1560
  • [32] A note on semidefinite programming relaxations for polynomial optimization over a single sphere
    Hu Jiang
    Jiang Bo
    Liu Xin
    Wen ZaiWen
    SCIENCE CHINA-MATHEMATICS, 2016, 59 (08) : 1543 - 1560
  • [33] ON THE LASSERRE HIERARCHY OF SEMIDEFINITE PROGRAMMING RELAXATIONS OF CONVEX POLYNOMIAL OPTIMIZATION PROBLEMS
    De Klerk, Etienne
    Laurent, Monique
    SIAM JOURNAL ON OPTIMIZATION, 2011, 21 (03) : 824 - 832
  • [34] Multi-objective convex polynomial optimization and semidefinite programming relaxations
    Jae Hyoung Lee
    Nithirat Sisarat
    Liguo Jiao
    Journal of Global Optimization, 2021, 80 : 117 - 138
  • [35] DC Semidefinite programming and cone constrained DC optimization I: theory
    Dolgopolik, M., V
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2022, 82 (03) : 649 - 671
  • [36] Global optimization in protein docking using clustering, underestimation and semidefinite programming
    Marcia, Roummel F.
    Mitchell, Julie C.
    Wright, Stephen J.
    OPTIMIZATION METHODS & SOFTWARE, 2007, 22 (05) : 803 - 811
  • [37] A note on semidefinite programming relaxations for polynomial optimization over a single sphere
    Jiang Hu
    Bo Jiang
    Xin Liu
    ZaiWen Wen
    Science China Mathematics, 2016, 59 : 1543 - 1560
  • [38] DC Semidefinite programming and cone constrained DC optimization I: theory
    M. V. Dolgopolik
    Computational Optimization and Applications, 2022, 82 : 649 - 671
  • [39] Multi-objective convex polynomial optimization and semidefinite programming relaxations
    Lee, Jae Hyoung
    Sisarat, Nithirat
    Jiao, Liguo
    JOURNAL OF GLOBAL OPTIMIZATION, 2021, 80 (01) : 117 - 138
  • [40] TRUSS TOPOLOGY OPTIMIZATION WITH SEMIDEFINITE PROGRAMMING AND PARAMETRIC MODEL ORDER REDUCTION
    Sanmugadas, Varakini
    Kapania, Rakesh K.
    PROCEEDINGS OF ASME 2023 AEROSPACE STRUCTURES, STRUCTURAL DYNAMICS, AND MATERIALS CONFERENCE, SSDM2023, 2023,
12345