On the set multicover problem in geometric settings

DOI10.1145/2390176.2390185MaRDI QIDQ2933638zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kenneth L. Clarkson, Sariel Har-Peled

Publication date 5 December 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

cuttingsLP roundingset cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27)

Abstract: We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p in P is covered by (contained in) at least d(p) sets. Here d(p) is an integer demand (requirement) for p. When the demands d(p)=1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this paper, we show that similar improvements can be obtained for the multi-cover problem as well. In particular, we obtain an O(log Opt) approximation for set systems of bounded VC-dimension, where Opt is the cardinality of an optimal solution, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.

Recommendations

• On the set multi-cover problem in geometric settings
• On the geometric set multicover problem
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover

Cited in

(31)

• Covering a set of points in multidimensional space
• Exact multi-covering problems with geometric sets
• Geometric optimization revisited
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• The maximum exposure problem
• On the geometric set multicover problem
• Near-linear algorithms for geometric hitting sets and set covers
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• Geometric red-blue set cover for unit squares and related problems
• The robust minimal controllability problem
• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• Novel geometric approach for virtual coiling
• Weighted geometric set multi-cover via quasi-uniform sampling
• Demand hitting and covering of intervals
• Approximation algorithms for polynomial-expansion and low-density graphs
• Guarding 1.5D terrains with demands
• Geometric Set Cover and Hitting Sets for Polytopes in R
• Tight approximation bounds for maximum multi-coverage
• On Geometric Set Cover for Orthants
• On partial covering for geometric set systems
• On the set multi-cover problem in geometric settings
• The Maximum Exposure Problem.
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Local search strikes again: PTAS for variants of geometric covering and packing
• The robust minimal controllability and observability problem
• On the geometric priority set cover problem
• Hardness and algorithms for electoral manipulation under media influence
• Geometric dominating-set and set-cover via local-search
• Geometric stabbing via threshold rounding and factor revealing LPs
• PTAS for minimum cost multicovering with disks
• On the number of incidences when avoiding an induced biclique in geometric settings

This page was built for publication: On the set multicover problem in geometric settings

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