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.

本文言語English
ホスト出版物のタイトルComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
編集者Weili Wu, Guangmo Tong
出版社Springer Science and Business Media Deutschland GmbH
ページ238-249
ページ数12
ISBN(印刷版)9783031491924
DOI
出版ステータス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
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

Conference

Conference29th International Computing and Combinatorics Conference, COCOON 2023
国/地域United States
CityHawaii
Period23/12/1523/12/17

ASJC Scopus subject areas

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

フィンガープリント

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

引用スタイル