Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring

DOI10.1007/11496915_12zbMath1119.90076OpenAlexW1489434708MaRDI QIDQ3596346

Garud Iyengar, David J. Phillips, Clifford Stein

Publication date: 30 August 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.8078

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Dimensionality reduction of SDPs through sketching ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

This page was built for publication: Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring