On the set multi-cover problem in geometric settings

DOI10.1145/1542362.1542421MaRDI QIDQ5370734zbMATH OpenOpenAlexFDO

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

Publication date 20 October 2017

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

Full work available at URL https://doi.org/10.1145/1542362.1542421

zbMATH Keywords

cuttingsLP roundingset cover

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(19)

• Covering a set of points in multidimensional space
• Almost optimal set covers in finite VC-dimension
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Exact multi-covering problems with geometric sets
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• On the geometric set multicover problem
• Approximating set multi-covers
• A PTAS for the cardinality constrained covering with unit balls
• Weighted geometric set multi-cover via quasi-uniform sampling
• On the set multicover problem in geometric settings
• Weighted geometric set multi-cover via quasi-uniform sampling
• Multi cover of a polygon minimizing the sum of areas
• Geometric Packing under Nonuniform Constraints
• Geometric Set Cover and Hitting Sets for Polytopes in R
• On Geometric Set Cover for Orthants
• On partial covering for geometric set systems
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• Local search strikes again: PTAS for variants of geometric covering and packing
• Geometric dominating-set and set-cover via local-search

This page was built for publication: On the set multi-cover problem in geometric settings

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