TY - GEN

T1 - Deterministic Primal-Dual Algorithms for Online k-Way Matching with Delays

AU - Kakimura, Naonori

AU - Nakayoshi, Tomohiro

N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024

Y1 - 2024

N2 - 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 requests arrive one-by-one over time in a metric space. At any time, we can irrevocably make a group of k requests who arrived so far, that incurs the distance cost among 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 the min-cost perfect matching with delays (corresponding to 2-MPMD). It is known that no online algorithm for k-MPMD can achieve a bounded competitive ratio in general, where the competitive ratio is the worst-case ratio between its performance and the offline optimal value. On the other hand, k-MPMD is known to admit a randomized online algorithm with competitive ratio O(k5log n) for a certain class of k-point metrics called the H-metric, where n is the size of the metric space. In this paper, we propose a deterministic online algorithm with a competitive ratio of O(mk2) for the k-MPMD in H-metric space. Furthermore, we show that the competitive ratio can be improved to O(m+ k2) if the metric is given as a diameter on a line.

AB - 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 requests arrive one-by-one over time in a metric space. At any time, we can irrevocably make a group of k requests who arrived so far, that incurs the distance cost among 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 the min-cost perfect matching with delays (corresponding to 2-MPMD). It is known that no online algorithm for k-MPMD can achieve a bounded competitive ratio in general, where the competitive ratio is the worst-case ratio between its performance and the offline optimal value. On the other hand, k-MPMD is known to admit a randomized online algorithm with competitive ratio O(k5log n) for a certain class of k-point metrics called the H-metric, where n is the size of the metric space. In this paper, we propose a deterministic online algorithm with a competitive ratio of O(mk2) for the k-MPMD in H-metric space. Furthermore, we show that the competitive ratio can be improved to O(m+ k2) if the metric is given as a diameter on a line.

KW - Competitive Analysis

KW - Online Algorithm

KW - Online Matching

UR - http://www.scopus.com/inward/record.url?scp=85180541646&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85180541646&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-49193-1_18

DO - 10.1007/978-3-031-49193-1_18

M3 - Conference contribution

AN - SCOPUS:85180541646

SN - 9783031491924

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 238

EP - 249

BT - Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings

A2 - Wu, Weili

A2 - Tong, Guangmo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 29th International Computing and Combinatorics Conference, COCOON 2023

Y2 - 15 December 2023 through 17 December 2023

ER -