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 study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings-- a key ingredient in numerous breakthroughs in the dynamic graph algorithmsliterature. Our first contribution is a surprisingly simple deterministicrounding algorithm in bipartite graphs with amortized update time$O(\epsilon^{-1} \log^2 (\epsilon^{-1} \cdot n))$, matching an (unconditional)recourse lower bound of $\Omega(\epsilon^{-1})$ up to logarithmic factors.Moreover, this algorithm's update time improves provided the minimum (non-zero)weight in the fractional matching is lower bounded throughout. Combining thisalgorithm with novel dynamic \emph{partial rounding} algorithms to increasethis minimum weight, we obtain several algorithms that improve this dependenceon $n$. For example, we give a high-probability randomized algorithm with$\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptiveadversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmicfactors in the argument, i.e., $\tilde{O}(f)=O(f\cdot \mathrm{poly}(\log f))$.)Using our rounding algorithms, we also round known $(1-\epsilon)$-decrementalfractional bipartite matching algorithms with no asymptotic overhead, thusimproving on state-of-the-art algorithms for the decremental bipartite matchingproblem. Further, we provide extensions of our results to general graphs and tomaintaining almost-maximal matchings.

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs