## Contributed Session Wed.1.H 3013

#### Wednesday, 10:30 - 12:00 h, Room: H 3013

**Cluster 2: Combinatorial optimization** [...]

### Network flows

**Chair: Chandra Chekuri**

**Wednesday, 10:30 - 10:55 h, Room: H 3013, Talk 1**

**Maria Afsharirad**

Maximum dynamic flow interdiction problem

**Coauthor: Hosein Taqizadeh Kakhki**

**Abstract:**

Let *G=(N,A)* be a directed graph with a given source node *s*, and a given sink node *t*. Let *N=(G,u,\tau,r)* be the associated dynamic network with arc capacities *u*, flow traversal times *\tau*, and arc interdiction costs *r*. The problem is to find a set of arcs whose removal will minimize the maximum flow from *s* to *t* within a given time period of *T*, subject to budget limitation. This is in fact the dynamic version of the well known max flow interdiction problem. We present a new formulation based on the concept of temporally repeated flows and discuss two solution approaches for this problem. Some numerical results will also be presented.

**Wednesday, 11:00 - 11:25 h, Room: H 3013, Talk 2**

**Andreas Karrenbauer**

Planar min-cost flow in nearly *O(n*^{3/2})

**Coauthor: Sabine Cornelsen**

**Abstract:**

We present combinatorial algorithms for the min-cost flow problem in planar graphs. Previously, the best known bounds came from algorithms for general graphs using only that the number of arcs is in *O(n)*. These yield near quadratic algorithms and subquadratic ones only for special cases, e.g., *Õ(n*^{7/4}) time if the optimum objective value is in *O(n)*, or *O(n*^{3/2}) time for bounded costs and capacities. We demonstrate techniques to obtain *O(n*^{3/2}) for planar graphs of bounded degree, constant capacities, and arbitrary costs, or for bidirected planar graphs of bounded face sizes, no capacities, and bounded costs. These conditions come from applications in image processing and in graph drawing, respectively. In the latter case, our result improves a long standing time bound for minimizing the number of bends in an orthogonal drawing of a plane graph. Without these restrictions but with the condition of a linear optimum, we only lose a log-factor, i.e. we get *O(n*^{3/2}*log* n). With a scaling approach, we obtain

*O( √U n **log*^{3} n *log* C), where *U* is the sum over all capacities and *C* is the maximum over all costs.

**Wednesday, 11:30 - 11:55 h, Room: H 3013, Talk 3**

**Chandra Chekuri**

Multicommodity flows and cuts in polymatroidal networks

**Coauthors: Sreeram Kannan, Adnan Raja, Pramod Viswanath**

**Abstract:**

The maxflow-mincut theorem for *s-t* flow is a

fundamental theorem in combinatorial optimization. Flow-cut

equivalence does not hold in the multicommodity case. Approximate

flow-cut gap results have been extensively studied, and

poly-logarithmic upper bounds have been established in various

settings.

Motivated by applications to information flow in wireless networks,

we consider flow-cut gap results in *polymatroidal*

networks in which there are submodular capacity constraints on the edges

incident to a node. Such networks were introduced by Lawler & Martel

and Hassin in the single-commodity setting, and are closely related to

the submodular flow model of Edmonds & Giles. The maxflow-mincut

theorem for a single-commodity holds in polymatroidal

networks. For these networks we obtain the first approximate

multicommodity flow-cut gap results that (nearly) match

several known results in standard networks. Of technical interest

is the use of line-embeddings to round the dual of the flow relaxation

rewritten with a convex objective function using the Lovasz-extension

of a submodular function.