2016/12/16 by Sumedh Tirodkar, Tirodkar, Sumedh, Sundar Vishwanathan +1
Computer Science · #Optimization and Search Problems #Distributed systems and fault tolerance #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1612.05419
We study the Maximum Cardinality Matching (MCM) and the Maximum Weight\nMatching (MWM) problems, on trees and on some special classes of graphs, in the\nOnline Preemptive and the Incremental Dynamic Graph models. In the em Online\nPreemptive model, the edges of a graph are revealed one by one and the\nalgorithm is required to always maintain a valid matching. On seeing an edge,\nthe algorithm has to either accept or reject the edge. If accepted, then the\nadjacent edges are discarded, and all rejections are permanent. In this model,\nthe complexity of the problems is settled for deterministic algorithms. Epstein\net al. gave a 5.356-competitive randomized algorithm for MWM, and also proved\na lower bound of 1.693 for MCM. The same lower bound applies for MWM.\n In this paper we show that some of the results can be improved in the case of\ntrees and some special classes of graphs. In the online preemptive model, we\npresent a 64/33-competitive (in expectation) randomized algorithm for MCM on\ntrees.\n Inspired by the above mentioned algorithm for MCM, we present the main result\nof the paper, a randomized algorithm for MCM with a "worst case" update time of\nO(1), in the incremental dynamic graph model, which is 3/2-approximate (in\nexpectation) on trees, and 1.8-approximate (in expectation) on general graphs\nwith maximum degree 3. Note that this algorithm works only against an\noblivious adversary. Hence, we derandomize this algorithm, and give a (3/2 +\n\ε)-approximate deterministic algorithm for MCM on trees, with an\namortized update time of O(1/\ε).\n We also present a minor result for MWM in the online preemptive model, a\n3-competitive (in expectation) randomized algorithm on growing trees (where\nthe input revealed upto any stage is always a tree, i.e. a new edge never\nconnects two disconnected trees).\n