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 threshold of ln n for approximating set cover
• 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
• Improved results on geometric hitting set problems
• A Separator Theorem for Planar Graphs
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Guarding terrains via local search
• A PTAS for the Weighted Unit Disk Cover Problem
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Planar Support for Non-piercing Regions and Applications
• Approximation schemes for clustering with outliers
• A finite family of pseudodiscs must include a ``small pseudodisc
• Title not available (Why is that?)

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)