English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We provide an algorithm that maintains, against an adaptive adversary, a$(1-\varepsilon)$-approximate maximum matching in $n$-node $m$-edge general(not necessarily bipartite) undirected graph undergoing edge deletions withhigh probability with (amortized) $O(\mathrm{poly}(\varepsilon^{-1}, \log n))$time per update. We also obtain the same update time for maintaining afractional approximate weighted matching (and hence an approximation to thevalue of the maximum weight matching) and an integral approximate weightedmatching in dense graphs. Our unweighted result improves upon the priorstate-of-the-art which includes a $\mathrm{poly}(\log{n}) \cdot2^{O(1/\varepsilon^2)}$ update time [Assadi-Bernstein-Dudeja 2022] and an$O(\sqrt{m} \varepsilon^{-2})$ update time [Gupta-Peng 2013], and our weightedresult improves upon the $O(\sqrt{m}\varepsilon^{-O(1/\varepsilon)}\log{n})$update time due to [Gupta-Peng 2013].  To obtain our results, we generalize a recent optimization approach todynamic algorithms from [Jambulapati-Jin-Sidford-Tian 2022]. We show thatrepeatedly solving entropy-regularized optimization problems yields a lazyupdating scheme for fractional decremental problems with a near-optimal numberof updates. To apply this framework we develop optimization methods compatiblewith it and new dynamic rounding algorithms for the matching polytope.

Entropy Regularization and Faster Decremental Matching in General Graphs