The value of strong inapproximability results for clique

DOI10.1145/335305.335322zbMATH Open1296.05157OpenAlexW2133034393MaRDI QIDQ3191981FDOQ3191981

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

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

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)

Cited In (5)

• A note on the approximation of the MAX CLIQUE problem
• On the approximability of clique and related maximization problems
• Strong computational lower bounds via parameterized complexity
• Title not available (Why is that?)
• Improved non-approximability results

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)