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 条
[41]   State estimation of DC microgrids using manifold optimization and semidefinite programming [J].
Montoya, Oscar Danilo ;
Garces-Ruiz, Alejandro ;
Gil-Gonzalez, Walter .
RESULTS IN ENGINEERING, 2024, 24
[42]   Ranging Energy Optimization for Robust Sensor Positioning Based on Semidefinite Programming [J].
Wang, Tao ;
Leus, Geert ;
Huang, Li .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2009, 57 (12) :4777-4787
[43]   Mathematical programming formulation for neural combinatorial optimization algorithms [J].
Urahama, K .
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, 1995, 78 (09) :67-75
[44]   Semidefinite programming in the space of partial positive semidefinite matrices [J].
Burer, S .
SIAM JOURNAL ON OPTIMIZATION, 2003, 14 (01) :139-172
[45]   On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0–1 quadratic problems leading to quasi-Newton methods [J].
Jérôme Malick ;
Frédéric Roupin .
Mathematical Programming, 2013, 140 :99-124
[46]   SEMIDEFINITE PROGRAMMING FOR THE NEAREST HURWITZ SEMIDEFINITE MATRIX PROBLEM [J].
Al-Homidan, Suliman .
JOURNAL OF NONLINEAR AND CONVEX ANALYSIS, 2024, 25 (01) :1-10
[47]   Semidefinite programming and matrix scaling over the semidefinite cone [J].
Kalantari, B .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 375 :221-243
[48]   Solving standard quadratic optimization problems via linear, semidefinite and copositive programming [J].
Bomze, IM ;
De Klerk, E .
JOURNAL OF GLOBAL OPTIMIZATION, 2002, 24 (02) :163-185
[49]   SEMIDEFINITE PROGRAMMING APPROXIMATION FOR A MATRIX OPTIMIZATION PROBLEM OVER AN UNCERTAIN LINEAR SYSTEM [J].
Xu, Jintao ;
Fang, Shu-cherng ;
Xing, Wenxun .
JOURNAL OF NONLINEAR AND VARIATIONAL ANALYSIS, 2024, 8 (06) :831-853
[50]   A robust algorithm for semidefinite programming [J].
Doan, Xuan Vinh ;
Kruk, Serge ;
Wolkowicz, Henry .
OPTIMIZATION METHODS & SOFTWARE, 2012, 27 (4-5) :667-693
12345