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 study the $k$-server problem with time-windows. In this problem, eachrequest $i$ arrives at some point $v_i$ of an $n$-point metric space at time$b_i$ and comes with a deadline $e_i$. One of the $k$ servers must be moved to$v_i$ at some time in the interval $[b_i, e_i]$ to satisfy this request. Wegive an online algorithm for this problem with a competitive ratio of ${\rmpolylog} (n,\Delta)$, where $\Delta$ is the aspect ratio of the metric space.Prior to our work, the best competitive ratio known for this problem was $O(k\cdot {\rm polylog}(n))$ given by Azar et al. (STOC 2017). Our algorithm isbased on a new covering linear program relaxation for $k$-server on HSTs. ThisLP naturally corresponds to the min-cost flow formulation of $k$-server, andeasily extends to the case of time-windows. We give an online algorithm forobtaining a feasible fractional solution for this LP, and a primal dualanalysis framework for accounting the cost of the solution. Together, theyyield a new $k$-server algorithm with poly-logarithmic competitive ratio, andextend to the time-windows case as well. Our principal technical contributionlies in thinking of the covering LP as yielding a {\em truncated} covering LPat each internal node of the tree, which allows us to keep account of servermovements across subtrees. We hope that this LP relaxation and thealgorithm/analysis will be a useful tool for addressing $k$-server and relatedproblems.

A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows