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 the problem of online Min-cost Perfect Matching with Delays(MPMD) recently introduced by Emek et al, (STOC 2016). This problem is definedon an underlying $n$-point metric space. An adversary presents real-timerequests online at points of the metric space, and the algorithm is required tomatch them, possibly after keeping them waiting for some time. The costincurred is the sum of the distances between matched pairs of points (theconnection cost), and the sum of the waiting times of the requests (the delaycost). We present an algorithm with a competitive ratio of $O(\log n)$, whichimproves the upper bound of $O(\log^2n+\log\Delta)$ of Emek et al, by removingthe dependence on $\Delta$, the aspect ratio of the metric space (which can beunbounded as a function of $n$). The core of our algorithm is a deterministicalgorithm for MPMD on metrics induced by edge-weighted trees of height $h$,whose cost is guaranteed to be at most $O(1)$ times the connection cost plus$O(h)$ times the delay cost of every feasible solution. The reduction from MPMDon arbitrary metrics to MPMD on trees is achieved using the result on embedding$n$-point metric spaces into distributions over weighted hierarchicallyseparated trees of height $O(\log n)$, with distortion $O(\log n)$. We alsoprove a lower bound of $\Omega(\sqrt{\log n})$ on the competitive ratio of anyrandomized algorithm. This is the first lower bound which increases with $n$,and is attained on the metric of $n$ equally spaced points on a line.  The problem of Min-cost Bipartite Perfect Matching with Delays (MBPMD) is thesame as MPMD except that every request is either positive or negative, andrequests can be matched only if they have opposite polarity. We prove an upperbound of $O(\log n)$ and a lower bound of $\Omega(\log^{1/3}n)$ on thecompetitive ratio of MBPMD with a more involved analysis.

Polylogarithmic Bounds on the Competitiveness of Min-cost (Bipartite) Perfect Matching with Delays