New lower bound and algorithm for online geometric hitting set problem

DOI10.1007/978-981-95-0215-8_18MaRDI QIDQ6867272zbMATH OpenFDO

Authors Minati De, Ratnadip Mandal, Satyam Singh

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0215-8_18

zbMATH Keywords

fat objectshitting sethypercubesonline algorithmrandomized lower bound

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A randomized algorithm for online unit clustering
• A threshold of ln n for approximating set cover
• Analytical approach to parallel repetition
• Dynamic data structures for fat objects and their applications
• Faster approximation algorithms for geometric set cover
• Hitting geometric objects online via points in \(\mathbb{Z}^d\)
• Hitting sets online and unique-MAX coloring
• Improved results on geometric hitting set problems
• Incremental Clustering and Dynamic Information Retrieval
• Near-linear algorithms for geometric hitting sets and set covers
• Online and dynamic algorithms for geometric set cover and hitting set
• Online geometric covering and piercing
• Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
• Online hitting set of \(d\)-dimensional fat objects
• Online unit clustering and unit covering in higher dimensions
• Online unit covering in Euclidean space
• Optimal packing and covering in the plane are NP-complete
• Polynomial-time approximation schemes for packing and piercing fat objects
• Realistic input models for geometric algorithms
• The online set cover problem

Cited in

(3)

• The online piercing set problem with recourse
• Online geometric hitting set using points in \(\mathbb{Z}^d\)
• Online hitting sets for disks of bounded radii

This page was built for publication: New lower bound and algorithm for online geometric hitting set problem

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