An SDP primal-dual algorithm for approximating the Lovász-theta function

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

zbMATH Keywords

maximum independent setsperfect graphsapproximation algorithmsLovász-theta functionprimal-dual SDP methods

Mathematics Subject Classification ID

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