Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
From MaRDI portal
Publication:5146765
DOI10.1137/1.9781611975994.5OpenAlexW3001868306MaRDI QIDQ5146765
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
Related Items (6)
FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Tight FPT approximation for socially fair clustering ⋮ Matroid-constrained vertex cover ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ To close is easier than to open: dual parameterization to \(k\)-median
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)
