research-article

Public Access

Routing under balance

Authors:

Alina Ene,

Gary Miller,

Jakub Pachocki,

Aaron SidfordAuthors Info & Claims

STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

Pages 598 - 611

https://doi.org/10.1145/2897518.2897654

Published: 19 June 2016 Publication History

PDF eReader

Abstract

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(α · log³ 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 α² / є²). 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.

References

[1]

{ACF + 03} Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Räcke. Optimal oblivious routing in polynomial time. In Lawrence L. Larmore and Michel X. Goemans, editors, Proc. of ACM STOC, pages 383–388. ACM, 2003.

Abstract

References

Cited By

Index Terms

Recommendations

Near-Optimal Distributed Maximum Flow: Extended Abstract

Oblivious routing on node-capacitated and directed graphs

An o(n^3)-Time Algorithm Maximun-Flow Algorithm

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations