English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs

MPS-Authors
/persons/resource/persons285340

Kiss,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2306.11828.pdf
(Preprint), 695KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bhattacharya, S., Kiss, P., Sidford, A., & Wajc, D. (2024). Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. Retrieved from https://arxiv.org/abs/2306.11828.


Cite as: https://hdl.handle.net/21.11116/0000-0010-866D-D
Abstract
We study dynamic $(1-\epsilon)$-approximate rounding of fractional matchings
-- a key ingredient in numerous breakthroughs in the dynamic graph algorithms
literature. Our first contribution is a surprisingly simple deterministic
rounding 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 this
algorithm with novel dynamic \emph{partial rounding} algorithms to increase
this minimum weight, we obtain several algorithms that improve this dependence
on $n$. For example, we give a high-probability randomized algorithm with
$\tilde{O}(\epsilon^{-1}\cdot (\log\log n)^2)$-update time against adaptive
adversaries. (We use Soft-Oh notation, $\tilde{O}$, to suppress polylogarithmic
factors 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)$-decremental
fractional bipartite matching algorithms with no asymptotic overhead, thus
improving on state-of-the-art algorithms for the decremental bipartite matching
problem. Further, we provide extensions of our results to general graphs and to
maintaining almost-maximal matchings.