Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.

DOI10.4230/LIPICS.ESA.2020.78OpenAlexW3082018149MaRDI QIDQ5874550FDOQ5874550

Authors Rajiv Raman, Saurabh Ray

Publication date 7 February 2023

Full work available at URL https://dblp.uni-trier.de/db/conf/esa/esa2020.html#0001R20

zbMATH Keywords

geometryapproximation algorithmscovering

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A PTAS for the Weighted Unit Disk Cover Problem
• A Separator Theorem for Planar Graphs
• A finite family of pseudodiscs must include a ``small pseudodisc
• A threshold of ln n for approximating set cover
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Almost tight bounds for \(\epsilon\)-nets
• Approximation schemes for clustering with outliers
• Guarding terrains via local search
• Hitting sets when the VC-dimension is small
• Improved results on geometric hitting set problems
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Optimality of geometric local search
• Planar Support for Non-piercing Regions and Applications
• Weighted geometric set cover via quasi-uniform sampling
• \(\epsilon\)-nets and simplex range queries

Cited in

(1)

• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks

This page was built for publication: Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.

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