Colloquium on "Fully Online Matching" given by Zhiyi Huang (University of
Hong Kong). The seminar will take place at 14:00 CET (local time in central
Europe), and will be followed by a discussion session. We would like to
invite you to take part in the event including the networking session. This
new event aims to integrate the European algorithmic community and keep it
connected during the times of the pandemic. The meeting will be held using
Airmeet platform and to attend please go to
https://www.airmeet.com/e/b28eee00-2dc9-11eb-939d-636c2b17ea0b. You can
find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.
We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.
The details of the talk are given below.
November 26, 2020, 14:00 CET
Zhiyi Huang (University of Hong Kong)
Title: Fully Online Matching
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.
Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Adi Rosén
Eva Rotenberg
Piotr Sankowski
Christian Sohler
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
