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 present a randomized on-line algorithm for the Metrical Task System problem that achieves a competitive ratio of against an oblivious adversary, on any metric space. This is the first algorithm to achieve a sublinear competitive ratio for all m etric spaces. Our algorithm uses a recent result of Bartal (Bar96) that an arbitrary metric space can b e probabilistically approximated by a set of metric spaces called " -hierarchical well-separated trees" ( -HST's). Indeed, the main technical result of this paper is an -competitive algorithm for -HST spaces. This, combined with the result of (Bar96), yields the general bound. Note that for the -server problem on metric spaces of points our result implies a competitive ratio of .

A polylog(n)-competitive algorithm for metrical task systems