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 the Min-cost Perfect $k$-way Matching with Delays($k$-MPMD), recently introduced by Melnyk et al. In the problem, $m$ requestsarrive one-by-one over time in a metric space. At any time, we can irrevocablymake a group of $k$ requests who arrived so far, that incurs the distance costamong the $k$ requests in addition to the sum of the waiting cost for the $k$requests. The goal is to partition all the requests into groups of $k$requests, minimizing the total cost. The problem is a generalization of themin-cost perfect matching with delays (corresponding to $2$-MPMD). It is knownthat no online algorithm for $k$-MPMD can achieve a bounded competitive ratioin general, where the competitive ratio is the worst-case ratio between itsperformance and the offline optimal value. On the other hand, $k$-MPMD is knownto admit a randomized online algorithm with competitive ratio $O(k^{5}\log n)$for a certain class of $k$-point metrics called the $H$-metric, where $n$ isthe size of the metric space. In this paper, we propose a deterministic onlinealgorithm with a competitive ratio of $O(mk^2)$ for the $k$-MPMD in $H$-metricspace. Furthermore, we show that the competitive ratio can be improved to $O(m+ k^2)$ if the metric is given as a diameter on a line.

Deterministic Primal-Dual Algorithms for Online k-way Matching with Delays