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

DOI10.1007/S00453-013-9756-5MaRDI QIDQ2249741zbMATH OpenOpenAlexFDO

Authors T.-H. Hubert Chan, Kevin Chang, 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

approximation algorithmsLovász-theta functionmaximum independent setsperfect graphsprimal-dual SDP methods

Mathematics Subject Classification ID

Perfect graphs (05C17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating the independence number via the -function
• On the Lovász theta function for independent sets in sparse graphs
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• On the Lovász theta function and some variants
• On the Lovász Theta Function for Independent Sets in Sparse Graphs

Cites work

• Approximate graph coloring by semidefinite programming
• Approximating semidefinite packing programs
• How the proof of the strong perfect graph conjecture was found
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 5485455 (Why is no real title available?)
• scientific article; zbMATH DE number 1256751 (Why is no real title available?)
• scientific article; zbMATH DE number 2079379 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• On the Shannon capacity of a graph
• Preconditioning Lanczos Approximations to the Matrix Exponential
• Recognizing Berge graphs
• The complexity of the matrix eigenproblem
• The multiplicative weights update method: a meta-algorithm and applications
• The sandwich theorem
• The strong perfect graph theorem

Cited in

(4)

• Approximating the independence number via the -function
• On the Lovász theta function and some variants
• Lovász theta function, SVMs and finding dense subgraphs
• On the Lovász theta function for independent sets in sparse graphs

This page was built for publication: An SDP primal-dual algorithm for approximating the Lovász-theta function

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