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

In this paper, we present a framework used to construct and analyzealgorithms for online optimization problems with deadlines or with delay over ametric space. Using this framework, we present algorithms for several differentproblems. We present an $O(D^{2})$-competitive deterministic algorithm foronline multilevel aggregation with delay on a tree of depth $D$, an exponentialimprovement over the $O(D^{4}2^{D})$-competitive algorithm of Bienkowski et al.(ESA '16), where the only previously-known improvement was for the special caseof deadlines by Buchbinder et al. (SODA '17). We also present an$O(\log^{2}n)$-competitive randomized algorithm for online service with delayover any general metric space of $n$ points, improving upon the$O(\log^{4}n)$-competitive algorithm by Azar et al. (STOC '17). In addition, wepresent the problem of online facility location with deadlines. In thisproblem, requests arrive over time in a metric space, and need to be serveduntil their deadlines by facilities that are opened momentarily for some cost.We also consider the problem of facility location with delay, in which thedeadlines are replaced with arbitrary delay functions. For those problems, wepresent $O(\log^{2}n)$-competitive algorithms, with $n$ the number of points inthe metric space. The algorithmic framework we present includes techniques forthe design of algorithms as well as techniques for their analysis.

General Framework for Metric Optimization Problems with Delay or with Deadlines