Approximation Algorithms for Label Cover and The Log-Density Threshold

DOI10.1137/1.9781611974782.57zbMath1411.68185OpenAlexW4250990868MaRDI QIDQ4575796

Pasin Manurangsi, Dana Moshkovitz, Eden Chlamtáč, 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

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

Related Items (5)

Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lasserre integrality gaps for graph spanners and related problems

This page was built for publication: Approximation Algorithms for Label Cover and The Log-Density Threshold