Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
type: Item
instance of: scholarly article
title: Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
zbMATH Open document ID: 1387.90182
author: Timothy Lee
author: John E. Mitchell
published in: Discrete Optimization
publication date: 2018-05-24T00:00:00Z
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6872132
zbMATH Keywords: semidefinite programming
zbMATH Keywords: approximation algorithms
zbMATH Keywords: \textsc{MaxCut}
zbMATH Keywords: \textsc{Max2Sat}
zbMATH Keywords: \textsc{Max3Sat}
describes a project that uses: SDPLR
MaRDI profile type: Publication
full work available at URL: j.disopt.2016.04.003
OpenAlex ID: W2356944478
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Q4737518
cites work: Gadgets, Approximation, and Linear Programming
cites work: On the copositive representation of binary and continuous nonconvex quadratic programs
cites work: On conic QPCCs, conic QCQPs and completely positive programs
cites work: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
cites work: The spectral bundle method with second-order information
cites work: Approximating Semidefinite Packing Programs
cites work: Q4429169
cites work: A unifying framework for several cutting plane methods for semidefinite programming
cites work: An optimal method for stochastic composite optimization
cites work: A second-order cone cutting surface method: Complexity and application
cites work: A parallel interior point decomposition algorithm for block angular semidefinite programs
cites work: Q4906149
cites work: Enhancing RLT relaxations via a new class of semidefinite cuts
cites work: An Interior Point Cutting Plane Method for the Convex Feasibility Problem with Second-Order Cone Inequalities
cites work: A Spectral Bundle Method for Semidefinite Programming
cites work: Complexity estimates of some cutting plane methods based on the analytic barrier
cites work: A semidefinite programming based polyhedral cut and price approach for the maxcut problem
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Some simplified NP-complete graph problems
cites work: The expected relative error of the polyhedral approximation of the max- cut problem
cites work: Computing the nearest correlation matrix--a problem from finance
cites work: Computing a nearest symmetric positive semidefinite matrix
cites work: Linear Programming Relaxations of Quadratically Constrained Quadratic Programs
DOI: 10.1016/J.DISOPT.2016.04.003
description: scientific article; zbMATH DE number 6872132