Speaker: Jiale Chen, Stanford University

Time: 16:00 p.m., July 5, 2024, GMT+8

Venue:  Room 204, Courtyard No.5, Jingyuan

Abstract: 

We provide an algorithm that maintains, against an adaptive adversary, a $(1-\eps)$-approximate maximum matching in $n$-node $m$-edge general (not necessarily bipartite) undirected graph undergoing edge deletions with high probability with (amortized) $O(\poly(\eps^{-1}, \log n))$ time per update. We also obtain the same update time for maintaining a fractional approximate weighted matching (and hence an approximation to the value of the maximum weight matching) and an integral approximate weighted matching in dense graphs.\footnote{Independently and concurrently, Aditi Dudeja obtained new decremental weighted matching results for general graphs~\cite{Dudeja23}.}
Our unweighted result improves upon the prior state-of-the-art which includes a $\poly(\log{n}) \cdot 2^{O(1/\eps^2)}$ update time [Assadi-Bernstein-Dudeja 2022] and an $O(\sqrt{m} \eps^{-2})$ update time [Gupta-Peng 2013], and our weighted result improves upon the $O(\sqrt{m}\eps^{-O(1/\eps)}\log{n})$ update time due to [Gupta-Peng 2013].
To obtain our results, we generalize a recent optimization approach to dynamic algorithms from [Jambulapati-Jin-Sidford-Tian 2022]. We show that repeatedly solving entropy-regularized optimization problems yields a lazy updating scheme for fractional decremental problems with a near-optimal number of updates. To apply this framework we develop optimization methods compatible with it and new dynamic rounding algorithms for the matching polytope.

Source: Center on Frontiers of Computing Studies, PKU