Approximation algorithms for label cover and the log-density threshold
DOI10.1137/1.9781611974782.57zbMATH Open1411.68185OpenAlexW4250990868MaRDI QIDQ4575796FDOQ4575796
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
Recommendations
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)
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
- Title not available (Why is that?)
- 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)
