DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.128

Online Preemptive Matching Revisited

Authors: Peter Kiss and Mohammad Sharifi

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study the online preemptive matching problem, in which the edges of a graph arrive sequentially and the algorithm must maintain a matching by accepting or rejecting arriving edges and possibly discarding previously accepted ones. We prove a new upper bound of 0.5661 on the competitive ratio achievable for the problem. This bound applies to arbitrary randomized algorithms, bipartite graphs and if we allow the algorithm to output a fractional solution. Our result improves upon the strongest previously known upper bound of 2-√2 ≈ 0.585, due to Huang et al. [SODA'19]. Previous hardness constructions relied on edge sequences described by vertex arrivals where each arriving vertex reveals its edges to yet unvaried vertices. Under such sequences, Huang et al. showed that there exists a non-preemptive online algorithm with competitive ratio ∼0.567 (or 2-√2 for fractional solutions). Consequently, our hardness construction is the first result which shows hardness for instances where the optimal algorithm employs preemption.

Cite as

Peter Kiss and Mohammad Sharifi. Online Preemptive Matching Revisited. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 128:1-128:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kiss_et_al:LIPIcs.ICALP.2026.128,
  author =	{Kiss, Peter and Sharifi, Mohammad},
  title =	{{Online Preemptive Matching Revisited}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{128:1--128:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.128},
  URN =		{urn:nbn:de:0030-drops-265172},
  doi =		{10.4230/LIPIcs.ICALP.2026.128},
  annote =	{Keywords: Online Algorithms, Preemptive Algorithms, Approximate Maximum Matching}
}

Search Results

Documents authored by Sharifi, Mohammad

Online Preemptive Matching Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message