Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)

DOI10.1016/j.tcs.2024.114452arXiv2303.11779OpenAlexW4391837034MaRDI QIDQ6190006

Satyam Singh, Minati De

Publication date: 5 March 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

geometric objectscompetitive ratioonline algorithmhitting setunit covering

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Improved results on geometric hitting set problems
• Hitting sets online and unique-MAX coloring
• Optimal packing and covering in the plane are NP-complete
• Algorithmic graph theory and perfect graphs
• Experiments with unit disk cover algorithms for covering massive pointsets
• Online unit clustering and unit covering in higher dimensions
• Near-linear algorithms for geometric hitting sets and set covers
• A threshold of ln n for approximating set cover
• On the Complexity of Some Common Geometric Location Problems
• The Online Set Cover Problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Incremental Clustering and Dynamic Information Retrieval
• Online and dynamic algorithms for set cover
• Reducibility among Combinatorial Problems
• Online unit covering in Euclidean space
• Hitting geometric objects online via points in \(\mathbb{Z}^d\)

This page was built for publication: Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)