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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The dispersion problem has been widely studied in computational geometry andfacility location, and is closely related to the packing problem. The goal isto locate n points (e.g., facilities or persons) in a k-dimensional polytope,so that they are far away from each other and from the boundary of thepolytope. In many real-world scenarios however, the points arrive and depart atdifferent times, and decisions must be made without knowing future events.Therefore we study, for the first time in the literature, the online dispersionproblem in Euclidean space.  There are two natural objectives when time is involved: the all-timeworst-case (ATWC) problem tries to maximize the minimum distance that everappears at any time; and the cumulative distance (CD) problem tries to maximizethe integral of the minimum distance throughout the whole time interval.Interestingly, the online problems are highly non-trivial even on a segment.For cumulative distance, this remains the case even when the problem istime-dependent but offline, with all the arriving and departure times given inadvance.  For the online ATWC problem on a segment, we construct a deterministicpolynomial-time algorithm which is (2ln2+epsilon)-competitive, where epsilon>0can be arbitrarily small and the algorithm's running time is polynomial in1/epsilon. We show this algorithm is actually optimal. For the same problem ina square, we provide a 1.591-competitive algorithm and a 1.183 lower-bound.Furthermore, for arbitrary k-dimensional polytopes with k>=2, we provide a2/(1-epsilon)-competitive algorithm and a 7/6 lower-bound. Interestingly, forthe offline CD problem in arbitrary k-dimensional polytopes, we provide apolynomial-time black-box reduction to the online ATWC problem, and theresulting competitive ratio increases by a factor of at most 2.

Efficient Approximations for the Online Dispersion Problem