IGAFIT Algorithmic Colloquium

IGAFIT Algorithmic Colloquium is a new online seminar series organized by IGAFIT. The event aims to provide a forum for research exchange and scientific interaction, to integrate the European algorithmic community, and to keep the community connected during the times of the pandemic. The goal is to present the highlights of algorithmic research and the most exciting works in this area.

The upcoming seminar, on 26 November 2020, features Zhiyi Huang (University of Hong Kong).

Abstract: Motivated by applications such as ride sharing, we introduce a fully online model of maximum cardinality matching in which all vertices arrive and depart online. On the arrival of a vertex, its edges to previously-arrived vertices are revealed. The vertex can be matched anytime before its departure, which is after all its neighbors’ arrivals. This fully online matching model generalizes the online bipartite matching model which only considers bipartite graphs and assumes one side of the vertices to be offline.

We generalize the Ranking and Water-Filling algorithms to fully online matching and its fractional relaxation respectively. The former is 0.521-competitive in general graphs, and 0.567-competitive in bipartite graphs, and the latter is 0.585 competitive in both cases. Further, we prove that fully online matching is strictly harder than online bipartite matching, because no online algorithm can be 0.6317 <(1-1/e)-competitive in fully online matching even for bipartite graphs. Finally, we introduce new algorithms that are strictly better than Ranking and Water-Filling in fully online matching.