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

approximation algorithmscombinatorial optimizationnonsmooth optimizationprimal-dual methodssemidefinite programming

Mathematics Subject Classification ID

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

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

(19)

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

Describes a project that uses

Uses Software

• SeDuMi
• DSPCA

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)