Change search
ReferencesLink to record
Permanent link

Direct link
New deterministic approximation algorithms for fully dynamic matching
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0003-4468-2675
2016 (English)Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
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
National Category
Discrete Mathematics
URN: urn:nbn:se:kth:diva-197222DOI: 10.1145/2897518.2897568ScopusID: 2-s2.0-84979210576OAI: diva2:1052936
48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, 19 June 2016 through 21 June 2016

QC 20161207

Available from: 2016-12-07 Created: 2016-11-30 Last updated: 2016-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Na Nongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link