New deterministic approximation algorithms for fully dynamic matching
Bhattacharya S, Henzinger MH, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.
Download (ext.)
https://arxiv.org/abs/1604.05765
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Bhattacharya, Sayan;
Henzinger, MonikaISTA ;
Nanongkai, Danupon
Abstract
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(logn, 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(logn)-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.
Publishing Year
Date Published
2016-06-01
Proceedings Title
48th Annual ACM SIGACT Symposium on Theory of Computing
Publisher
Association for Computing Machinery
Page
398 - 411
Conference
STOC: Symposium on Theory of Computing
Conference Location
Cambridge, MA, United States
Conference Date
2016-06-19 – 2016-06-21
ISBN
ISSN
IST-REx-ID
Cite this
Bhattacharya S, Henzinger MH, Nanongkai D. New deterministic approximation algorithms for fully dynamic matching. In: 48th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery; 2016:398-411. doi:10.1145/2897518.2897568
Bhattacharya, S., Henzinger, M. H., & Nanongkai, D. (2016). New deterministic approximation algorithms for fully dynamic matching. In 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 398–411). Cambridge, MA, United States: Association for Computing Machinery. https://doi.org/10.1145/2897518.2897568
Bhattacharya, Sayan, Monika H Henzinger, and Danupon Nanongkai. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” In 48th Annual ACM SIGACT Symposium on Theory of Computing, 398–411. Association for Computing Machinery, 2016. https://doi.org/10.1145/2897518.2897568.
S. Bhattacharya, M. H. Henzinger, and D. Nanongkai, “New deterministic approximation algorithms for fully dynamic matching,” in 48th Annual ACM SIGACT Symposium on Theory of Computing, Cambridge, MA, United States, 2016, pp. 398–411.
Bhattacharya S, Henzinger MH, Nanongkai D. 2016. New deterministic approximation algorithms for fully dynamic matching. 48th Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 398–411.
Bhattacharya, Sayan, et al. “New Deterministic Approximation Algorithms for Fully Dynamic Matching.” 48th Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery, 2016, pp. 398–411, doi:10.1145/2897518.2897568.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1604.05765