A node-capacitated Okamura–Seymour theorem

James R. Lee, Manor Mendel, Mohammad Moharrami

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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 $$\varepsilon > 0$$ε>0, if the node cut conditions are satisfied, then one can simultaneously route an $$\varepsilon $$ε-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.

שפה מקוריתאנגלית
עמודים (מ-עד)381-415
מספר עמודים35
כתב עתMathematical Programming
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 22 נוב׳ 2015

הערה ביבליוגרפית

Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A node-capacitated Okamura–Seymour theorem'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי