2026-07-22T06:19:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16418 2024-03-06T10:57:26Z ddc:004 open_access

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching Jambulapati, Arun Jin, Yujia Sidford, Aaron Tian, Kevin bipartite matching decremental matching dynamic algorithms continuous optimization box-simplex games primal-dual method Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [Sherman, 2017], optimal transport [Arun Jambulapati et al., 2019], and bipartite matching [Sepehr Assadi et al., 2022]. We develop efficient near-linear time, high-accuracy solvers for regularized variants of these games. Beyond the immediate applications of such solvers for computing Sinkhorn distances, a prominent tool in machine learning, we show that these solvers can be used to obtain improved running times for maintaining a (fractional) ε-approximate maximum matching in a dynamic decremental bipartite graph against an adaptive adversary. We give a generic framework which reduces this dynamic matching problem to solving regularized graph-structured optimization problems to high accuracy. Through our reduction framework, our regularized box-simplex game solver implies a new algorithm for dynamic decremental bipartite matching in total time Õ(m ⋅ ε^{-3}), from an initial graph with m edges and n nodes. We further show how to use recent advances in flow optimization [Chen et al., 2022] to improve our runtime to m^{1 + o(1)} ⋅ ε^{-2}, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of Õ(m ⋅ ε^{-4}) [Aaron Bernstein et al., 2020] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arun Jambulapati and Yujia Jin and Aaron Sidford and Kevin Tian 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.77 urn:nbn:de:0030-drops-164181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.77 eng https://creativecommons.org/licenses/by/4.0/legalcode