Online hitting set of d-dimensional fat objects

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

Authors: Shanli Alefkhani, Nima Khodaveisi, Mathieu Mari 

Publication date: 19 July 2024

zbMATH Keywords

online algorithmsEuclidean planeminimum hitting set

Mathematics Subject Classification ID

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

Cites Work

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

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

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