# Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

arXiv: https://arxiv.org/abs/2204.12721 · HTML: https://mlsanity.com/paper/2204.12721/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2022.

## Built on by (most cited first, 1 of 1)

- [Multi-Domain Learning with Global Expert Mapping](https://mlsanity.com/paper/2604.18842/) (2026)

## Abstract (arXiv)

Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite matching [AJJ+22]. 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 tildeO(m · ε-3), from an initial graph with m edges and n nodes. We further show how to use recent advances in flow optimization [CKL+22] to improve our runtime to m1 + o(1) · ε-2, thereby demonstrating the versatility of our reduction-based approach. These results improve upon the previous best runtime of tildeO(m · ε-4) [BGS20] and illustrate the utility of using regularized optimization problem solvers for designing dynamic algorithms.