Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions

Yi-Jun Chang, Hsin-Hao Su

Many combinatorial optimization problems can be approximated within $(1\pm \epsilon )$ factors in $\text{poly}(\log n,1/\epsilon )$ rounds in the LOCAL model via network decompositions [Ghaffari…