Faster approximation algorithms for geometric set cover

DOI10.4230/LIPICS.SOCG.2020.27MaRDI QIDQ6059975zbMATH OpenFDO

Authors Timothy M. Chan, Qizheng He

Publication date 2 November 2023

Full work available at URL https://arxiv.org/abs/2003.13420

zbMATH Keywords

approximation algorithmsmultiplicate weight update methodrandom samplingset covershallow cuttings

Mathematics Subject Classification ID

Statistical sampling theory and related topics (62D99) Complexity and performance of numerical algorithms (65Y20) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Improved approximation algorithms for geometric set cover
• Improved approximation algorithms for geometric set cover
• Near-linear algorithms for geometric hitting sets and set covers
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces

Cited in

(18)

• On the geometric set multicover problem
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Improved approximation algorithms for geometric set cover
• scientific article; zbMATH DE number 7662168 (Why is no real title available?)
• Minimum ply covering of points with unit squares
• On the geometric priority set cover problem
• On the line-separable unit-disk coverage and related problems
• New lower bound and algorithm for online geometric hitting set problem
• Computing data distribution from query selectivities
• On the line-separable unit-disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• Dynamic geometric set cover, revisited
• More dynamic data structures for geometric set cover with sublinear update time
• Online geometric hitting set using points in \(\mathbb{Z}^d\)
• On line-separable weighted unit-disk coverage and related problems
• Improved approximation algorithms for geometric set cover

This page was built for publication: Faster approximation algorithms for geometric set cover

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