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

Naonori Kakimura, Tomohiro Nakayoshi

研究成果: Conference contribution


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.

ホスト出版物のタイトルComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
編集者Weili Wu, Guangmo Tong
出版社Springer Science and Business Media Deutschland GmbH
出版ステータスPublished - 2024
イベント29th International Computing and Combinatorics Conference, COCOON 2023 - Hawaii, United States
継続期間: 2023 12月 152023 12月 17


名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
14423 LNCS


Conference29th International Computing and Combinatorics Conference, COCOON 2023
国/地域United States

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般


「Deterministic Primal-Dual Algorithms for Online k-Way Matching with Delays」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。