Approximation algorithms for label cover and the log-density threshold

DOI10.1137/1.9781611974782.57MaRDI QIDQ4575796zbMATH OpenOpenAlexFDO

Authors Eden Chlamtac, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.57

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Improved approximation algorithms for label cover problems
• Improved Approximation Algorithms for Label Cover Problems
• On the hardness of approximating label-cover
• Improved approximation algorithms for projection games
• A threshold of ln n for approximating set cover

Cited in

(12)

• Sherali-Adams integrality gaps matching the log-density threshold
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Lasserre integrality gaps for graph spanners and related problems
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• On the hardness of approximating label-cover
• scientific article; zbMATH DE number 7561533 (Why is no real title available?)
• Improved Approximation Algorithms for Label Cover Problems
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Improved approximation algorithms for projection games
• Improved approximation algorithms for label cover problems
• Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner

This page was built for publication: Approximation algorithms for label cover and the log-density threshold

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