The Shortest Augmenting Paths for Online Matchings on Trees
The Shortest Augmenting Paths for Online Matchings on Trees
复制标题
树上在线匹配的最短增广路径
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Sankowski
中科院分区：
文献类型：
--
作者：
B. Bosek;Dariusz Leniowski;Anna Zych;P. Sankowski
This paper is devoted to understanding the shortest augmenting path approach for computing a maximum matching. Despite its apparent potential for designing efficient matching and flow algorithms, it has been poorly understood. Chaudhuri et. al. [K. Chaudhuri, C. Daskalakis, R. D. Kleinberg, and H. Lin. Online bipartite perfect matching with augmentations. In INFOCOM 2009.] study this classical approach in the following model. A bipartite graph $G=W uplus B$ is revealed online and in each round a vertex of $b$ is presented together with the adjacent edges. It is then matched by applying the shortest among the augmenting paths. Chaudhuri et. al. conjecture that the total length of the augmenting paths is $O(n log n)$, where $n$ is the number of vertices in the final graph. Recently a bound of $O(n log^2 n)$ has been proven given that the underlying graph is a tree [B. Bosek, D. Leniowski, P. Sankowski, and A. Zych. Shortest augmenting paths for online matchings on trees. In WAOA 2015]. We further improve this bound to $O(n log n)$. To achieve that, we introduce brand new techniques that we believe are applicable to bipartite graphs as well.
