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

Naonori Kakimura, Tomohiro Nakayoshi

Research output: Chapter in Book/Report/Conference proceedingConference 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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
EditorsWeili Wu, Guangmo Tong
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages12
ISBN (Print)9783031491924
Publication statusPublished - 2024
Event29th International Computing and Combinatorics Conference, COCOON 2023 - Hawaii, United States
Duration: 2023 Dec 152023 Dec 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14423 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference29th International Computing and Combinatorics Conference, COCOON 2023
Country/TerritoryUnited States


  • Competitive Analysis
  • Online Algorithm
  • Online Matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Deterministic Primal-Dual Algorithms for Online k-Way Matching with Delays'. Together they form a unique fingerprint.

Cite this