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

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

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

(15)

• On the hardness of approximating label-cover
• Lasserre integrality gaps for graph spanners and related problems
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• Improved Approximation Algorithms for Label Cover Problems
• Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
• Sherali-Adams integrality gaps matching the log-density threshold
• The norms of graph spanners
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Improved approximation algorithms for projection games
• Improved approximation algorithms for label cover problems
• Sum-of-squares lower bounds for densest k-subgraph
• On approximate reconfigurability of label cover
• The strongish planted clique hypothesis and its consequences
• Tight hardness results for training depth-2 ReLU networks

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)