Deferred On-Line Bipartite Matching

  • Jakub Kozik
  • Grzegorz Matecki
Keywords: On-line, Bipartite matching, Adaptive algorithm

Abstract

We present a new model for the problem of on-line matching on bipartite graphs. Suppose that one part of a graph is given, but the vertices of the other part are presented in an on-line fashion. In the classical version, each incoming vertex is either irrevocably matched to a vertex from the other part or stays unmatched forever. In our version, an algorithm is allowed to match the new vertex to a group of elements (possibly empty). Later on, the algorithm can decide to remove some vertices from the group and assign them to another (just presented) vertex, with the restriction that each element belongs to at most one group. We present an optimal (deterministic) algorithm for this problem and prove that its competitive ratio equals $1-\pi/\cosh(\frac{\sqrt{3}}{2}\pi)\approx 0.588$.

Author Biographies

Jakub Kozik, Jagiellonian University in Krakow
Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University in Krakow
Grzegorz Matecki, Jagiellonian University in Krakow
Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University in Krakow
Published
2018-05-11
Article Number
P2.24