Online hitting set of \(d\)-dimensional fat objects

DOI10.1007/978-3-031-49815-2_10MaRDI QIDQ6574940

Mathieu Mari, Nima Khodaveisi, Shanli Alefkhani

Publication date: 19 July 2024

zbMATH Keywords

online algorithmsEuclidean planeminimum hitting set

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Hitting sets online and unique-MAX coloring
• Optimal packing and covering in the plane are NP-complete
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Hitting Sets Online and Vertex Ranking
• The Online Set Cover Problem
• A Greedy Heuristic for the Set-Covering Problem
• Polynomial-time approximation schemes for packing and piercing fat objects
• Reducibility among Combinatorial Problems
• PTAS for geometric hitting set problems via local search
• Hitting geometric objects online via points in \(\mathbb{Z}^d\)

This page was built for publication: Online hitting set of \(d\)-dimensional fat objects