Approximating semidefinite packing programs

DOI10.1137/090762671MaRDI QIDQ3004983zbMATH OpenOpenAlexFDO

Authors G. Iyengar, David J. Phillips, Clifford Stein

Publication date 6 June 2011

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/5b85c6da916e5761029af5b8da5a658134238695

zbMATH Keywords

combinatorial optimizationsemidefinite programmingapproximation algorithmsnonsmooth optimizationprimal-dual methods

Mathematics Subject Classification ID

Semidefinite programming (90C22) Numerical methods involving duality (49M29)

Recommendations

• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Feasible and accurate algorithms for covering semidefinite programs
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Semidefinite programming and combinatorial optimization
• Approximation algorithms and semidefinite programming.

Cited in

(16)

• A class of semidefinite programs with rank-one solutions
• A semidefinite programming hierarchy for packing problems in discrete geometry
• Sparse Approximate Solutions to Semidefinite Programs
• Fast First-Order Algorithms for Packing–Covering Semidefinite Programs
• Positive semidefinite relaxation and approximation algorithm for triple patterning lithography
• An SDP primal-dual algorithm for approximating the Lovász-theta function
• Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems
• Sublinear time algorithms for approximate semidefinite programming
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
• Feasible and accurate algorithms for covering semidefinite programs
• A new way of using semidefinite programming with applications to linear equations mod p
• Portfolio selection with multiple spectral risk constraints
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• An efficiently computable subgraph pattern support measure: counting independent observations
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms

Describes a project that uses

Uses Software

• DSPCA
• SeDuMi

This page was built for publication: Approximating semidefinite packing programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3004983)