Invited Session Fri.3.H 3013

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

Cluster 2: Combinatorial optimization [...]

Flows, cuts, and sparsifiers


Chair: Nicholas Harvey



Friday, 15:15 - 15:40 h, Room: H 3013, Talk 1

Nicholas Harvey
Graph sparsifiers


A sparsifier of a graph is a sparse, weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of 1 ± ε. Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc.
We describe a new approach to constructing sparsifiers: by sampling each edge uv with probability inversely proportional to the edge-connectivity between u and v. This results in a sparsifier with O(n log2(n) / ε2) edges, answering a question of Benczur and Karger. A variant of this argument shows that one can obtain sparsifiers by sampling uniformly random spanning trees. Our proofs are based on extensions of Karger's contraction algorithm which allow it to compute minimum "Steiner'' cuts.



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

Jonathan Kelner
Electrical flows, linear systems, and faster approximations of maximum flows, minimum s-t cuts, and multicommodity flows in undirected graphs

Coauthors: Paul Christiano, Aleksander Madry, Gary Miller, Richard Peng, Daniel Spielman, Shanghua Teng


In this talk, I'll describe a new collection of techniques for approximately solving maximum flow, minimum s-t cut, and multicommodity flow problems in capacitated, undirected graphs. Using these techniques, we obtain asymptotically faster algorithms for all three, breaking running time barriers that have stood for over 30 years.
For graphs with n vertices and m edges, I'll show how to compute \e-approximately maximum flows in time \o(m4/3)\p(1/\e) and \e-approximately minimum s-t cuts in time \o(m+n4/3)\p(1/\e). We do this by treating our graph as a network of resistors and solving a sequence of electrical flow problems with varying resistances on the edges. Each of these may be reduced to the solution of a system of linear equations in a Laplacian matrix, which can be solved in nearly-linear time.
I'll then discuss why generalizing this approach to the multicommodity setting requires more general classes of linear systems and iterative methods. Using these, we find \e-approximate solutions to the maximum concurrent flow problem with k commodities in time \o(m4/3\p(k,\e-1)).



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

Christophe Weibel
When the cut condition is enough: Characterization of multiflow problems by forbidden minors

Coauthors: Amit Chakrabarti, Lisa Fleischer


For a supply graph G=(V,E) and a demand graph H=(V,F),
an assignment of capacities to the
edges of G and demands to the edges of H is said to satisfy the
cut condition if for any cut in the graph, the total demand
crossing the cut is no more than the total capacity crossing it.
The pair (G,H) is called cut-sufficient if for any
assignment of capacities and demands that satisfy the cut condition,
the demands defined on H can be routed within the
network with capacities defined on G.
A pair (G, H) is said to contain another pair (G', H') as a minor
if it is possible to obtain (G', H') from (G, H) by contracting
edges of G and deleting edges of G and H. We propose
to characterize cut-sufficient pairs by forbidden minors.
In particular, we prove a previous conjecture giving the minimal set of forbidden minors
for instances with a series-parallel supply graph, and propose a
conjecture extending our results to planar supply graphs.


  personal loan . In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.