Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Volume: 63, Issue: 2, Pages: 460 - 482
Published: May 9, 2019
Abstract
Given a finite range space $\Sigma =(\mathsf {X},\mathcal {R}), with N= |\mathsf {X}| + |\mathcal {R}|, we present two simple algorithms, based on the multiplicative-weight method, for computing a small-size hitting set or set cover of \Sigma . The first algorithm is a simpler variant of the Brönnimann–Goodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a two-player zero-sum game....
Paper Details
Title
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
Published Date
May 9, 2019
Volume
63
Issue
2
Pages
460 - 482
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.