文章基本信息

标题：Online Algorithms for Maximum Cardinality Matching with Edge Arrivals
本地全文：下载
作者：Niv Buchbinder ; Danny Segev ; Yevgeny Tkach 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：22:1-22:14
DOI：10.4230/LIPIcs.ESA.2017.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1/2-competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5/9-competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2/(3+1/phi^2) ~ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, this bound holds even for an easier model in which vertices (along with their adjacent edges) arrive online, and when the underlying graph is a tree of maximum degree at most 3.
关键词：Maximum matching; online algorithms; competitive analysis; primal-dual method