A nodecapacitated OkamuraSeymour theorem
Abstract
The classical OkamuraSeymour theorem states that for an edgecapacitated, multicommodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are satisfied. Simple examples show that a similar theorem is impossible in the nodecapacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal c > 0, if the node cut conditions are satisfied, then one can simultaneously route a cfraction of all the demands. This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multicommodity polymatroid networks introduced by Chekuri, et. al. Our approach employs a new type of random metric embedding in order to round the convex programs corresponding to these more general flow problems.
 Publication:

arXiv eprints
 Pub Date:
 September 2012
 arXiv:
 arXiv:1209.2744
 Bibcode:
 2012arXiv1209.2744L
 Keywords:

 Mathematics  Combinatorics;
 Computer Science  Discrete Mathematics;
 Mathematics  Metric Geometry
 EPrint:
 30 pages, 5 figures