Abstract: We consider the problem of hitting sets online. The hypergraph (i.e., range-space consisting of points and ranges) is known in advance, and the ranges to be stabbed are input one-by-one in an online fashion. The online algorithm must stab each range upon arrival. An online algorithm may add points to the hitting set but may not remove already chosen points. The goal is to use the smallest number of points. The best known competitive ratio for hitting sets online by Alon et al. cite{alon2009online} is for general hypergraphs, where and denote the number of points and the number of ranges, respectively. We consider hypergraphs in which the union of two intersecting ranges is also a range. Our main result for such hypergraphs is as follows. The competitive ratio of the online hitting set problem is at most the unique-max number and at least this number minus one.
Recommendations
Cites work
- scientific article; zbMATH DE number 1232130 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A constant-factor approximation algorithm for optimal terrain guarding
- A threshold of ln n for approximating set cover
- Almost optimal set covers in finite VC-dimension
- Approximation algorithms for combinatorial problems
- Approximation schemes for covering and packing problems in image processing and VLSI
- Computational models and task scheduling for parallel sparse Cholesky factorization
- Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
- Covering rectilinear polygons with axis-parallel rectangles
- Hitting sets when the VC-dimension is small
- Improved approximation algorithms for geometric set cover
- On a graph partition problem with application to VLSI layout
- On neighbors in geometric permutations.
- On the ratio of optimal integral and fractional covers
- Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
- Optimal node ranking of tree in linear time
- Optimal node ranking of trees
- Ordered colourings
- The online set cover problem
Cited in
(9)- Tight bounds for online weighted tree augmentation
- On the diameter of tree associahedra
- Tight bounds for online weighted tree augmentation
- Online hitting set of \(d\)-dimensional fat objects
- Hitting geometric objects online via points in \(\mathbb{Z}^d\)
- Online class cover problem
- Online geometric covering and piercing
- Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\)
- Hitting sets online and vertex ranking
This page was built for publication: Hitting sets online and unique-MAX coloring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741535)
