Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

作者：Lee Timothy; Mitchell John E^*

来源：Discrete Optimization, 2017, 24: 152-169.

DOI：10.1016/j.disopt.2016.04.003

• Semidefinite programming
• Approximation algorithms
• MAxCuT
• MAx2SAT
• MAx3SAT

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MAxCuT, MAx2SAT, and MAx3SAT. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.

• 出版日期2017-5