Concave Flow on Small Depth Directed Networks

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 an...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Tung Mai, Peng, Richard, Rao, Anup B, Vazirani, Vijay V
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Networks
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422