Invited Session Fri.3.H 3008

Friday, 15:15 - 16:45 h, Room: H 3008

Cluster 2: Combinatorial optimization [...]

Faster algorithms for network flow problems


Chair: James Orlin and Laszlo Végh



Friday, 15:45 - 16:10 h, Room: H 3008, Talk 2

Yahav Nussbaum
Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time

Coauthors: Glencora Borradaile, Philip N. Klein, Shay Mozes, Christian Wulff-Nilsen


We consider the problem of finding a maximum flow from a set of source nodes to a set of sink nodes in an n-node directed planar graph with arc capacities. The multiple-source multiple-sink maximum flow problem can be solved using a standard single-source single-sink maximum flow algorithm, as there is a simple reduction which connects a single super-source to the set of sources and the set of sinks to a single super-sink. However, this reduction does not preserve the planarity of the graph, and we have to use a maximum flow algorithm for general (non-planar) graphs in conjunction with the reduction, which requires O(n2 log n) time. We present an O(n log3 n) algorithm for the problem. This is the first algorithm for the problem that exploits the planarity of the graph to get a faster time bound. Our algorithm combines wide range of techniques, including pseudoflows, flow partitioning scheme, the duality between flow circulation and shortest paths in planar graphs, succinct representation of a flow in a planar graph, and other planarity-exploiting algorithms.
This work was presented at FOCS 2011.



Friday, 16:15 - 16:40 h, Room: H 3008, Talk 3

Laszlo Végh
Concave generalized flows with applications to market equilibria


We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper and Shigeno. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an ε-approximate solution in O(m(m+log n)log(MUm/ε)) arithmetic operations and value oracle queries, where M and U are upper bounds on simple parameters.
This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant
of the Fat-Path algorithm by Goldberg, Plotkin and Tardos, not using any cycle cancellations.
We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately extends these market models to more general settings. We also obtain a combinatorial algorithm for nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani.


  There are three major facts that should be watched out for in all payday loans in the United States. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.