Approximating low-dimensional coverage problems

DOI10.1145/2261250.2261274MaRDI QIDQ2874577zbMATH OpenOpenAlexFDO

Authors Ashwinkumar Badanidiyuru, Hooyeon Lee, Robert D. Kleinberg

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractable

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We study the complexity of the maximum coverage problem, restricted to set systems of bounded VC-dimension. Our main result is a fixed-parameter tractable approximation scheme: an algorithm that outputs a $(1-eps)$-approximation to the maximum-cardinality union of $k$ sets, in running time $O(f(eps,k,d)cdotpoly(n))$ where $n$ is the problem size, $d$ is the VC-dimension of the set system, and $f(eps,k,d)$ is exponential in $(kd/eps{)}^c$ for some constant $c$. We complement this positive result by showing that the function $f(eps,k,d)$ in the running-time bound cannot be replaced by a function depending only on $(eps,d)$ or on $(k,d)$, under standard complexity assumptions. We also present an improved upper bound on the approximation ratio of the greedy algorithm in special cases of the problem, including when the sets have bounded cardinality and when they are two-dimensional halfspaces. Complementing these positive results, we show that when the sets are four-dimensional halfspaces neither the greedy algorithm nor local search is capable of improving the worst-case approximation ratio of $1-1/e$ that the greedy algorithm achieves on arbitrary instances of maximum coverage.

Recommendations

• Almost optimal set covers in finite VC-dimension
• A threshold of ln n for approximating set cover
• scientific article; zbMATH DE number 1947430
• Covering things with things
• Hitting sets when the VC-dimension is small

Cited in

(16)

• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Partial sublinear time approximation and inapproximation for maximum coverage
• Almost optimal set covers in finite VC-dimension
• On the Hadwiger covering problem in low dimensions
• How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem
• Critical nodes in interdependent networks with deterministic and probabilistic cascading failures
• Covering things with things
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• A Coverage Theory for Least Squares
• scientific article; zbMATH DE number 7376034 (Why is no real title available?)
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• On Geometric Set Cover for Orthants
• A note on the \(k\)-restriction problem
• Separating \(k\)-\textsc{Median} from the supplier version
• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs

This page was built for publication: Approximating low-dimensional coverage problems

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