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

In this paper, we study $k$-Way Min-cost Perfect Matching with Delays - the$k$-MPMD problem. This problem considers a metric space with $n$ nodes.Requests arrive at these nodes in an online fashion. The task is to match theserequests into sets of exactly $k$, such that the space and time cost of allmatched requests are minimized. The notion of the space cost requires adefinition of an underlying metric space that gives distances of subsets of $k$elements. For $k>2$, the task of finding a suitable metric space is at the coreof our problem: We show that for some known generalizations to $k=3$ points,such as the $2$-metric and the $D$-metric, there exists no competitiverandomized algorithm for the $3$-MPMD problem. The $G$-metrics are defined for3 points and allows for a competitive algorithm for the $3$-MPMD problem. For$k>3$ points, there exist two generalizations of the $G$-metrics known as $n$-and $K$-metrics. We show that neither the $n$-metrics nor the $K$-metrics canbe used for the $k$-MPMD problem. On the positive side, we introduce the$H$-metrics, the first metrics to allow for a solution of the $k$-MPMD problemfor all $k$. In order to devise an online algorithm for the $k$-MPMD problem onthe $H$-metrics, we embed the $H$-metric into trees with an $O(\log n)$distortion. Based on this embedding result, we extend the algorithm proposed byAzar et al. (2017) and achieve a competitive ratio of $O(\log n)$ for the$k$-MPMD problem.

Online k-Way Matching with Delays and the H-Metric