Title: Concave Flow on Small Depth Directed Networks,
Abstract: Small depth networks arise in a variety of network related applications,
often in the form of maximum flow and maximum weighted matching. Recent works
have generalized such methods to include costs arising from concave functions.
In this paper we give an algorithm that takes a depth $D$ network and strictly
increasing concave weight functions of flows on the edges and computes a $(1 -
\epsilon)$-approximation to the maximum weight flow in time $mD \epsilon^{-1}$
times an overhead that is logarithmic in the various numerical parameters
related to the magnitudes of gradients and capacities.
Our approach is based on extending the scaling algorithm for approximate
maximum weighted matchings by [Duan-Pettie JACM`14] to the setting of small
depth networks, and then generalizing it to concave functions. In this more
restricted setting of linear weights in the range $[w_{\min}, w_{\max}]$, it
produces a $(1 - \epsilon)$-approximation in time $O(mD \epsilon^{-1} \log(
w_{\max} /w_{\min}))$. The algorithm combines a variety of tools and provides a
unified approach towards several problems involving small depth networks.