New deterministic approximation algorithms for fully dynamic matching
2016 (English)Conference paper (Refereed)
We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + ϵ)-approximate maximum matching in general graphs with O(poly(log n, 1/ϵ)) update time. (2) An algorithm that maintains an αk approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 ≤ αk ≤ 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.
Place, publisher, year, edition, pages
2016. 398-411 p.
Proceedings of the Annual ACM Symposium on Theory of Computing
Data structures, Dynamic graph algorithms, Aluminum, Approximation algorithms, Approximation theory, Computation theory, Graph theory, Polynomial approximation, Bipartite graphs, Deterministic algorithms, Deterministic approximation, Dynamic algorithm, Dynamic matching, Maximum matchings, Positive integers, Algorithms
IdentifiersURN: urn:nbn:se:kth:diva-197222DOI: 10.1145/2897518.2897568ScopusID: 2-s2.0-84979210576OAI: oai:DiVA.org:kth-197222DiVA: diva2:1052936
48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, 19 June 2016 through 21 June 2016
QC 201612072016-12-072016-11-302016-12-07Bibliographically approved