Hitting sets online and unique-MAX coloring

DOI10.1016/J.DAM.2014.06.019zbMATH Open1300.05299arXiv1207.2598OpenAlexW2053576536MaRDI QIDQ741535FDOQ741535

Authors: Shakhar Smorodinsky, Guy Even 

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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 $O(logncdotlogm)$ for general hypergraphs, where $n$ and $m$ 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.

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

Recommendations

• Hitting sets online and vertex ranking
• Online hypergraph coloring
• Online conflict-free colouring for hypergraphs
• Online Conflict-Free Colorings for Hypergraphs
• On-line coloring of geometric intersection graphs

zbMATH Keywords

online algorithmsvertex rankingtransversalshitting set problemset cover problemunique MAX-coloring

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Transversal (matching) theory (05D15)

Cites Work

• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• Title not available (Why is that?)
• Hitting sets when the VC-dimension is small
• Optimal node ranking of trees
• On the ratio of optimal integral and fractional covers
• Almost optimal set covers in finite VC-dimension
• Title not available (Why is that?)
• Approximation schemes for covering and packing problems in image processing and VLSI
• The online set cover problem
• On a graph partition problem with application to VLSI layout
• Optimal node ranking of tree in linear time
• Ordered colourings
• Covering rectilinear polygons with axis-parallel rectangles
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Improved approximation algorithms for geometric set cover
• Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles
• On neighbors in geometric permutations.
• Computational models and task scheduling for parallel sparse Cholesky factorization
• A constant-factor approximation algorithm for optimal terrain guarding

Cited In (9)

• Tight bounds for online weighted tree augmentation
• Tight bounds for online weighted tree augmentation
• On the diameter of tree associahedra
• 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)