Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

DOI10.1137/1.9781611975994.5MaRDI QIDQ5146765zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi

Publication date 2 February 2021

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

Full work available at URL https://arxiv.org/abs/1910.11850

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Nearly optimal NP-hardness of unique coverage
• A threshold of ln n for approximating set cover
• Nearly optimal NP-hardness of unique coverage
• New and improved bounds for the minimum set cover problem
• Improved approximation algorithms for label cover problems

Cited in

(22)

• \(O(n \log n)\) procedures for tightening cover inequalities
• To close is easier than to open: dual parameterization to \(k\)-median
• Parameterized inapproximability of independent set in \(H\)-free graphs
• FPT Approximation for Constrained Metric k-Median/Means
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Tight FPT approximation for socially fair clustering
• Matroid-constrained vertex cover
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Max-SAT with cardinality constraint parameterized by the number of clauses
• On MAX-SAT with cardinality constraint
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• On MAX-SAT with cardinality constraint
• Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
• Baby PIH: Parameterized inapproximability of min CSP
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Parameterized inapproximability hypothesis under ETH
• Max-SAT with cardinality constraint parameterized by the number of clauses
• On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
• On the fine-grained complexity of approximating max k-coverage
• On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP
• On average baby PIH and its applications
• Sampling with a black box: faster parameterized approximation algorithms for vertex deletion problems

This page was built for publication: Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

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