Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
From MaRDI portal
Publication:1751224
DOI10.1016/j.disopt.2016.04.003zbMath1387.90182MaRDI QIDQ1751224
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
semidefinite programming; approximation algorithms; \textsc{Max2Sat}; \textsc{Max3Sat}; \textsc{MaxCut}
Uses Software
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
