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$.
@article{10_37236_5756,
author = {Jakub Kozik and Grzegorz Matecki},
title = {Deferred on-line bipartite matching},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/5756},
zbl = {1457.68317},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5756/}
}
TY - JOUR
AU - Jakub Kozik
AU - Grzegorz Matecki
TI - Deferred on-line bipartite matching
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5756/
DO - 10.37236/5756
ID - 10_37236_5756
ER -
%0 Journal Article
%A Jakub Kozik
%A Grzegorz Matecki
%T Deferred on-line bipartite matching
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5756/
%R 10.37236/5756
%F 10_37236_5756
Jakub Kozik; Grzegorz Matecki. Deferred on-line bipartite matching. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/5756
