## 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**

**Abstract:**

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(n*^{2} *log* n) time. We present an *O(n **log*^{3} 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

**Abstract:**

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.