Approximation Algorithms from Inexact Solutions
to Semidefinite Programming Relaxations of Combinatorial Optimization
Problems
Download the paper,
in pdf.
Authors:
Timothy Lee
(email)
WPA Research, Washington, DC 20003, USA.
John E. Mitchell
(email)
Department of Mathematical Sciences,
Rensselaer Polytechnic Institute,
Troy, New York 12180-3590, U.S.A.
The work of Lee was supported by the National Science
Foundation under Grant Number DMS--0636358.
The work of Mitchell was supported by the Air Force Office of Sponsored Research
under grant FA9550-11-1-0260 and by the National Science Foundation
under Grant Number CMMI--1334327.
This support is both acknowledged and appreciated.
Abstract:
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.
Download the paper,
in pdf |
Return
to my list of papers |
John E. Mitchell