Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Routing under Balance   We introduce the notion of balance for directed graphs: a weighted directed
graph is $\alpha$-balanced if for every cut $S \subseteq V$, the total weight
of edges going from $S$ to $V\setminus S$ is within factor $\alpha$ of the
total weight of edges going from $V\setminus S$ 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(\alpha \cdot \log^3 n / \log \log n)$ 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(\sqrt{n})$
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(\sqrt{n})$ 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.

3
The categories of this paper are: physics
31
The categories of this paper are: ao-sci
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
33
The categories of this paper are: plasm-ph
27
The categories of this paper are: comp-gas
23
The categories of this paper are: solv-int
6
The categories of this paper are: astro-ph
11
The categories of this paper are: hep-lat
17
The categories of this paper are: q-fin
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
22
The categories of this paper are: chao-dyn
32
The categories of this paper are: atom-ph