English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider an online version of the geometric minimum hitting set problemthat can be described as a game between an adversary and an algorithm. For someintegers $d$ and $N$, let $P$ be the set of points in $(0, N)^d$ with integralcoordinates, and let $\mathcal{O}$ be a family of subsets of $P$, calledobjects. Both $P$ and $\mathcal{O}$ are known in advance by the algorithm andby the adversary. Then, the adversary gives some objects one by one, and thealgorithm has to maintain a valid hitting set for these objects using pointsfrom $P$, with an immediate and irrevocable decision. We measure theperformance of the algorithm by its competitive ratio, that is the ratiobetween the number of points used by the algorithm and the offline minimumhitting set for the sub-sequence of objects chosen by the adversary.  We present a simple deterministic online algorithm with competitive ratio$((4\alpha+1)^{2d}\log N)$ when objects correspond to a family of $\alpha$-fatobjects. Informally, $\alpha$-fatness measures how cube-like is an object. Weshow that no algorithm can achieve a better ratio when $\alpha$ and $d$ arefixed constants. In particular, our algorithm works for two-dimensional disksand $d$-cubes which answers two open questions from related previous papers inthe special case where the set of points corresponds to all the points ofintegral coordinates with a fixed $d$-cube.

Online hitting set of $d$-dimensional fat objects