An SDP primal-dual algorithm for approximating the Lovász-theta function
From MaRDI portal
Publication:2249741
DOI10.1007/s00453-013-9756-5zbMath1294.05080OpenAlexW2105656976MaRDI QIDQ2249741
Kevin L. Chang, T.-H. Hubert Chan, Rajiv Raman
Publication date: 3 July 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9756-5
maximum independent setsperfect graphsapproximation algorithmsLovász-theta functionprimal-dual SDP methods
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Perfect graphs (05C17)
Cites Work
- The strong perfect graph theorem
- The sandwich theorem
- Recognizing Berge graphs
- The complexity of the matrix eigenproblem
- Approximating Semidefinite Packing Programs
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Preconditioning Lanczos Approximations to the Matrix Exponential
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An SDP primal-dual algorithm for approximating the Lovász-theta function