论文标题
持续跳扩张器的剪切游戏
A Cut-Matching Game for Constant-Hop Expanders
论文作者
论文摘要
本文扩展并概括了众所周知的切割匹配游戏框架，并提供了一种新颖的切割策略，可产生恒定的跳台扩张器。 恒定跳扩张器是普通扩张器的显着加强，并提供了额外的保证，即任何需求都可以（遗忘）沿恒定的流动路径进行路由 - 与$ω（\ log n）$ - 在扩展器中的跃点路径相反。 扩展器的剪切游戏是用于获得许多硬性问题的线性时间近似算法的关键工具，包括查找（平衡或近似最大的）稀疏切割，通过嵌入（显式的）expander以及计算expander分解，以及计算级别切割分解的范围，多数 - 多数 - 综合量和多数 - 综合量，证明了图形的扩展。 本文的剪切游戏对于将这种多功能和强大的机械扩展到恒定和长度约束的扩张器至关重要，并且已经被广泛使用。 For example, as a key ingredient in several recent breakthroughs, including, computing constant-approximate $k$-commodity (min-cost) flows in $(m+k)^{1+ε}$ time as well as the optimal constant-approximate deterministic worst-case fully-dynamic APSP-distance oracle - in all applications the constant-approximation factor directly traces to and crucially relies on the expanders从剪切匹配的游戏中，可以保证持续的跳路路径。
This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders. Constant-hop expanders are a significant strengthening of regular expanders with the additional guarantee that any demand can be (obliviously) routed along constant-hop flow-paths - in contrast to the $Ω(\log n)$-hop paths in expanders. Cut-matching games for expanders are key tools for obtaining linear-time approximation algorithms for many hard problems, including finding (balanced or approximately-largest) sparse cuts, certifying the expansion of a graph by embedding an (explicit) expander, as well as computing expander decompositions, hierarchical cut decompositions, oblivious routings, multi-cuts, and multi-commodity flows. The cut-matching game of this paper is crucial in extending this versatile and powerful machinery to constant-hop and length-constrained expanders and has been already been extensively used. For example, as a key ingredient in several recent breakthroughs, including, computing constant-approximate $k$-commodity (min-cost) flows in $(m+k)^{1+ε}$ time as well as the optimal constant-approximate deterministic worst-case fully-dynamic APSP-distance oracle - in all applications the constant-approximation factor directly traces to and crucially relies on the expanders from a cut-matching game guaranteeing constant-hop routing paths.
