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


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(n3/2)

Coauthor: Sabine Cornelsen


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., Õ(n7/4) time if the optimum objective value is in O(n), or O(n3/2) time for bounded costs and capacities. We demonstrate techniques to obtain O(n3/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(n3/2log n). With a scaling approach, we obtain
O( √U n log3 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


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


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.