Congestion-Approximators from the Bottom Up
<|reference_start|>Congestion-Approximators from the Bottom Up: We develop a novel algorithm to construct a congestion-approximator with polylogarithmic quality on a capacitated, undirected graph in nearly-linear time. Our approach is the first *bottom-up* hierarchical construction, in contrast to previous *top-down* approaches including that of Racke, Shah, and Taubig (SODA 2014), the only other construction achieving polylogarithmic quality that is implementable in nearly-linear time (Peng, SODA 2016). Similar to Racke, Shah, and Taubig, our construction at each hierarchical level requires calls to an approximate max-flow/min-cut subroutine. However, the main advantage to our bottom-up approach is that these max-flow calls can be implemented directly *without recursion*. More precisely, the previously computed levels of the hierarchy can be converted into a *pseudo-congestion-approximator*, which then translates to a max-flow algorithm that is sufficient for the particular max-flow calls used in the construction of the next hierarchical level. As a result, we obtain the first non-recursive algorithms for congestion-approximator and approximate max-flow that run in nearly-linear time, a conceptual improvement to the aforementioned algorithms that recursively alternate between the two problems.<|reference_end|>
@article{li2024congestion-approximators,
    title={Congestion-Approximators from the Bottom Up},
    author={Jason Li, Satish Rao, Di Wang},
    journal={arXiv preprint arXiv:2407.04976},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04976},
    primaryClass={cs.DS}
}