Routing under balance

DOI10.1145/2897518.2897654MaRDI QIDQ5361864zbMATH OpenOpenAlexFDO

Authors Alina Ene, Jakub W. Pachocki, Aaron Sidford, Gary L. Miller

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.09009

zbMATH Keywords

balanced directed graphsdirected graphsgradient descentgraph clusteringmaximum flowoblivious routing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We introduce the notion of balance for directed graphs: a weighted directed graph is $alpha$-balanced if for every cut $SsubseteqV$, the total weight of edges going from $S$ to $VsetminusS$ is within factor $alpha$ of the total weight of edges going from $VsetminusS$ to $S$. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with $alpha=1$) and residual graphs of $(1+epsilon)$-approximate undirected maximum flows (with $alpha=O(1/epsilon)$). 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(alphacdotlo{g}^{3}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 $Omega(n)$ in general; this result improves upon the long-standing best known lower bound of $Omega(sqrtn)$ given by Hajiaghayi, Kleinberg, Leighton and R"acke in 2006. We also show that our restriction to single-source instances is necessary by showing an $Omega(sqrtn)$ lower bound for multiple-source oblivious routing in Eulerian graphs. We also give a fast algorithm for the maximum flow problem in balanced directed graphs.

Recommendations

• Oblivious routing on node-capacitated and directed graphs
• Oblivious routing on node-capacitated and directed graphs
• Oblivious routing in directed graphs with random demands
• Optimal oblivious routing in polynomial time
• Semi-oblivious routing: lower bounds

Cited in

(9)

• A fast algorithm for source-wise round-trip spanners
• Oblivious routing on node-capacitated and directed graphs
• Semi-oblivious routing: lower bounds
• Oblivious routing on node-capacitated and directed graphs
• Local flow partitioning for faster edge connectivity
• Sparsification of directed graphs via cut balance
• Survivable network design with group-to-group requirement
• Incremental approximate maximum flow via residual graph sparsification
• Incremental approximate maximum flow via residual graph sparsification

This page was built for publication: Routing under balance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361864)