Nearly optimal NP-hardness of unique coverage

DOI10.1137/1.9781611974331.CH119MaRDI QIDQ4575703zbMATH OpenOpenAlexFDO

Authors Euiwoong Lee, Venkatesan Guruswami

Publication date 16 July 2018

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Nearly optimal NP-hardness of unique coverage
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• scientific article; zbMATH DE number 1670858
• scientific article; zbMATH DE number 2086690
• A threshold of ln n for approximating set cover

Cited in

(7)

• The parameterized complexity of unique coverage and its variants
• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• The quest for strong inapproximability results with perfect completeness
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Nearly optimal NP-hardness of unique coverage

This page was built for publication: Nearly optimal NP-hardness of unique coverage

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