The value of strong inapproximability results for clique

DOI10.1145/335305.335322MaRDI QIDQ3191981zbMATH OpenOpenAlexFDO

Authors Aravind Srinivasan

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335322

zbMATH Keywords

approximation algorithmsrandom samplingcliqueindependent setpacking integer programsP vs. NP

Mathematics Subject Classification ID

Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On the approximability of clique and related maximization problems
• A note on the approximation of the MAX CLIQUE problem
• On Unapproximable Versions of $NP$-Complete Problems
• scientific article; zbMATH DE number 1670809
• Improved non-approximability results

Cited in

(5)

• scientific article; zbMATH DE number 1670809 (Why is no real title available?)
• Strong computational lower bounds via parameterized complexity
• Improved non-approximability results
• On the approximability of clique and related maximization problems
• A note on the approximation of the MAX CLIQUE problem

This page was built for publication: The value of strong inapproximability results for clique

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