Routing under balance
Routing under balance
复制标题
路由处于平衡状态
DOI：
10.1145/2897518.2897654
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Aaron Sidford
中科院分区：
文献类型：
--
作者：
Alina Ene;G. Miller;J. Pachocki;Aaron Sidford
我们引入有向图平衡的概念：如果对每个切点S≥≥V，从S到V≤S的边的总权值在从V≤S到S的边的总权值的因子α内，则一个加权有向图是α-平衡的。有几个重要的图族是接近平衡的，特别是欧拉图（α= 1）和(1+ n)-近似无向最大流（α=O(1/ n)）的残差图。我们使用平衡的概念来对几个在有向图中相当困难的路由问题进行更细致的理解。我们首先回顾有向图中的无关路由。我们的主要算法结果是实现O（α·log3 n / loglog）竞争比的单源实例的遗忘路由方案。在这个过程中，我们做出了一些技术贡献，这些贡献可能是独立的。特别地，我们给出了用平衡参数化有向图的低半径分解的有效算法。我们还定义并构造了低拉伸树形，这是低拉伸生成树在有向图中的推广。在消极方面，我们给出了有向图上的遗忘路由问题的新的下界。我们证明了有向图的遗忘路由算法的竞争比一般为Ω(n)；该结果改进了Hajiaghayi等人长期以来最著名的Ω（√n）下界。我们还通过在欧拉图中显示多源无关路由的Ω（√n）下界来证明对单源实例的限制是必要的。我们还研究了任意容量的平衡有向图的最大流问题。我们开发了一种有效的算法，可以在时间O（m α2 / є2）上找到α-平衡图中的(1+ n)-近似最大流量。我们证明，使用我们的近似最大流量算法可以有效地确定给定的有向图是否为α-平衡。此外，我们还给出了有向稀疏切割问题的一个应用。
We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut S ⊆ V, the total weight of edges going from S to V∖ S is within factor α of the total weight of edges going from V∖ S to S. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with α = 1) and residual graphs of (1+є)-approximate undirected maximum flows (with α=O(1/є)). We use the notion of balance to give a more fine-grained understanding of several well-studied routing questions that are considerably harder in directed graphs. We first revisit oblivious routings in directed graphs. Our main algorithmic result is an oblivious routing scheme for single-source instances that achieve an O(α · log3 n / loglogn) competitive ratio. In the process, we make several technical contributions which may be of independent interest. In particular, we give an efficient algorithm for computing low-radius decompositions of directed graphs parameterized by balance. We also define and construct low-stretch arborescences, a generalization of low-stretch spanning trees to directed graphs. On the negative side, we present new lower bounds for oblivious routing problems on directed graphs. We show that the competitive ratio of oblivious routing algorithms for directed graphs is Ω(n) in general; this result improves upon the long-standing best known lower bound of Ω(√n) by Hajiaghayi et al. We also show that our restriction to single-source instances is necessary by showing an Ω(√n) lower bound for multiple-source oblivious routing in Eulerian graphs. We also study the maximum flow problem in balanced directed graphs with arbitrary capacities. We develop an efficient algorithm that finds an (1+є)-approximate maximum flows in α-balanced graphs in time O(m α2 / є2). We show that, using our approximate maximum flow algorithm, we can efficiently determine whether a given directed graph is α-balanced. Additionally, we give an application to the directed sparsest cut problem.