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

DOI10.4230/LIPIcs.ESA.2020.78OpenAlexW3082018149MaRDI QIDQ5874550

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

geometrycoveringapproximation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Improved results on geometric hitting set problems
• Hitting sets when the VC-dimension is small
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Weighted geometric set cover via quasi-uniform sampling
• Guarding terrains via local search
• A threshold of ln n for approximating set cover
• A PTAS for the Weighted Unit Disk Cover Problem
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• A Separator Theorem for Planar Graphs
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Planar Support for Non-piercing Regions and Applications
• A Finite Family of Pseudodiscs Must Include a “Small” Pseudodisc