@online{Bhattacharya2306.11828,
TITLE = {Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs},
AUTHOR = {Bhattacharya, Sayan and Kiss, Peter and Sidford, Aaron and Wajc, David},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2306.11828},
EPRINT = {2306.11828},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings<br>-- a key ingredient in numerous breakthroughs in the dynamic graph algorithms<br>literature. Our first contribution is a surprisingly simple deterministic<br>rounding algorithm in bipartite graphs with amortized update time<br>$O(\epsilon^{-1} \log^2 (\epsilon^{-1} \cdot n))$, matching an (unconditional)<br>recourse lower bound of $\Omega(\epsilon^{-1})$ up to logarithmic factors.<br>Moreover, this algorithm's update time improves provided the minimum (non-zero)<br>weight in the fractional matching is lower bounded throughout. Combining this<br>algorithm with novel dynamic \emph{partial rounding} algorithms to increase<br>this minimum weight, we obtain several algorithms that improve this dependence<br>on $n$. For example, we give a high-probability randomized algorithm with<br>$\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptive<br>adversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmic<br>factors in the argument, i.e., $\tilde{O}(f)=O(f\cdot \mathrm{poly}(\log f))$.)<br>Using our rounding algorithms, we also round known $(1-\epsilon)$-decremental<br>fractional bipartite matching algorithms with no asymptotic overhead, thus<br>improving on state-of-the-art algorithms for the decremental bipartite matching<br>problem. Further, we provide extensions of our results to general graphs and to<br>maintaining almost-maximal matchings.<br>},
}