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

DOI10.1016/j.disopt.2016.04.003zbMath1387.90182OpenAlexW2356944478MaRDI QIDQ1751224

John E. Mitchell, Timothy Lee

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.04.003

zbMATH Keywords

semidefinite programmingapproximation algorithms\textsc{Max2Sat}\textsc{Max3Sat}\textsc{MaxCut}

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Uses Software

• SDPLR

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the nearest correlation matrix--a problem from finance
• On conic QPCCs, conic QCQPs and completely positive programs
• An optimal method for stochastic composite optimization
• Enhancing RLT relaxations via a new class of semidefinite cuts
• A second-order cone cutting surface method: Complexity and application
• A parallel interior point decomposition algorithm for block angular semidefinite programs
• Computing a nearest symmetric positive semidefinite matrix
• Some simplified NP-complete graph problems
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• The expected relative error of the polyhedral approximation of the max- cut problem
• Complexity estimates of some cutting plane methods based on the analytic barrier
• On the copositive representation of binary and continuous nonconvex quadratic programs
• A semidefinite programming based polyhedral cut and price approach for the maxcut problem
• Linear Programming Relaxations of Quadratically Constrained Quadratic Programs
• The spectral bundle method with second-order information
• Approximating Semidefinite Packing Programs
• A unifying framework for several cutting plane methods for semidefinite programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Gadgets, Approximation, and Linear Programming
• A Spectral Bundle Method for Semidefinite Programming
• An Interior Point Cutting Plane Method for the Convex Feasibility Problem with Second-Order Cone Inequalities