CombOpt ReadingGroup - David Aleman-Unsplittable multicommodity flows in fully planar instances

The multicommodity flow problem involves routing multiple distinct commodities through a shared network. An instance is given by an undirected graph G=(V, E(G) ) with edge capacities, and a collection of source-sink pairs (s_i,t_i) in V with associated nonnegative demands d(s_i, t_i). It will be convenient to think of the source-sink pairs as forming the edges of a demand graph H=( V, E(H) ). A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let C be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most an additivie amount of C times the maximum demand value. 

We show that if G+H = (V, E(G) U E(H) ) is planar, then  1.5<= C <= 2.

Joint work with Kumar, Poremba, and Shepherd.