On the set multicover problem in geometric settings
From MaRDI portal
Publication:2933638
DOI10.1145/2390176.2390185zbMath1301.68237arXiv0909.0537OpenAlexW1993324779MaRDI QIDQ2933638
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
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
The maximum exposure problem ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ Novel geometric approach for virtual coiling ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ On the geometric set multicover problem ⋮ The robust minimal controllability problem ⋮ Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning ⋮ 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 ⋮ Demand Hitting and Covering of Intervals ⋮ The Maximum Exposure Problem. ⋮ Guarding 1.5D terrains with demands ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Exact multi-covering problems with geometric sets ⋮ An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting
