A node-capacitated Okamura-Seymour theorem

• 成果类型: Article
• 署名作者: Lee, James R.; Mendel, Manor; Moharrami, Mohammad
• 署名单位: University of Washington; University of Washington Seattle; Open University Israel
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0810-0
• 发表日期: 2015
• 页码: 381-415
• 关键词: approximation algorithms; graphs; geometry; cuts

摘要

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity 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 node-capacitated setting. Nevertheless, we prove that an approximate flow/cut theorem does hold: For some universal epsilon > 0, if the node cut conditions are satisfied, then one can simultaneously route an epsilon-fraction of all the demands. This answers a question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of the multi-commodity polymatroid networks introduced by Chekuri et al. (ITCS, pp 399-408, 2012). In their framework, one associates to each node a submodular function on the adjacent edges that dictates the types of flows the node can support. In order to round the convex programs corresponding to node and polymatroid-capacitated flows, we devise a new type of random metric embedding that preserves some of the combinatorial structure of the underlying graph.