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

DOI10.4230/LIPICS.ESA.2020.78MaRDI QIDQ5874550zbMATH OpenOpenAlexFDO

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

approximation algorithmscoveringgeometry

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• -nets and simplex range queries
• A finite family of pseudodiscs must include a ``small pseudodisc
• A PTAS for the Weighted Unit Disk Cover Problem
• A Separator Theorem for Planar Graphs
• 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 -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

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)