Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Antoine El-Hayek, Monika Henzinger, Jason Li · 2024
Read Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation by Antoine El-Hayek, Monika Henzinger, Jason Li (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15069.txt.
Description
Antoine El-Hayek, Monika Henzinger, and Jason Li give a fully dynamic approximate minimum cut in two thousand twenty-four. Graphs gain and lose edges while the minimum cut must be tracked. Past best near exact methods took far longer per update. Exact fast methods needed a promise of a large cut.
Their algorithm holds a near exact cut in subpolynomial update time. It is the first of its kind for the fully dynamic case. The core trick: small volume cuts in contracted graphs suffice. That lens shrinks the search the updates must run. Conditional lower bounds do not bar the gain.
Catalog record
| CREATOR | Antoine El-Hayek, Monika Henzinger, Jason Li |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 168 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15069