EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Online matching on 3-uniform hypergraphs

Sander Borst, Danish Kashaev, Zhuan Khye Koh

Mathematical Programming · 27.04.2026

DOI: 10.1007/s10107-026-02360-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 27.04.2026. Verfasst von Sander Borst und 2 weiteren Autor:innen. Die Arbeit nennt 38 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HORIZON EUROPE European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The online matching problem was introduced by Karp, Vazirani and Vazirani (STOC 1990) on bipartite graphs with vertex arrivals. It is well-known that the optimal competitive ratio is $$1-1/e$$ 1 - 1 / e for both integral and fractional versions of the problem. Since then, there has been considerable effort to find optimal competitive ratios for other related settings. In this work, we go beyond the graph case and study the online matching problem on k -uniform hypergraphs. For $$k=3$$ k = 3 , we provide an optimal primal-dual fractional algorithm, which achieves a competitive ratio of $$(e-1)/(e+1)\approx 0.4621$$ ( e - 1 ) / ( e + 1 ) ≈ 0.4621 . As our main technical contribution, we present a carefully constructed adversarial instance, which shows that this ratio is in fact optimal. It combines ideas from known hard instances for bipartite graphs under the edge-arrival and vertex-arrival models. For $$k\ge 3$$ k ≥ 3 , we give a simple integral algorithm which performs better than greedy when the online nodes have bounded degree. As a corollary, it achieves the optimal competitive ratio of 1/2 on 3-uniform hypergraphs when every online node has degree at most 2. This is because the special case where every online node has degree 1 is equivalent to the edge-arrival model on graphs, for which an upper bound of 1/2 is known.

Förderung

  • HORIZON EUROPE European Research Council

Zitieren

APA

Borst, S., Kashaev, D., & Koh, Z. K. (2026). Online matching on 3-uniform hypergraphs. Mathematical Programming. https://doi.org/10.1007/s10107-026-02360-2

Vancouver

Borst S, Kashaev D, Koh ZK. Online matching on 3-uniform hypergraphs. Mathematical Programming. 2026. doi:10.1007/s10107-026-02360-2

BibTeX
@article{Borst2026,
  author = {Borst, Sander and Kashaev, Danish and Koh, Zhuan Khye},
  title = {Online matching on 3-uniform hypergraphs},
  journal = {Mathematical Programming},
  year = {2026},
  doi = {10.1007/s10107-026-02360-2}
}
Kostenlos starten →