Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
From MaRDI portal
Publication:5874550
DOI10.4230/LIPIcs.ESA.2020.78OpenAlexW3082018149MaRDI QIDQ5874550
Publication date: 7 February 2023
Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2020.html#0001R20
Related Items
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