A node-capacitated okamura-seymour theorem

James R. Lee, Manor Mendel, Mohamad 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 " ε > 0, if the node cut conditions are satisfied, then one can simultaneously route an " ε- fraction of all the demands. This answers an open question of Chekuri and Kawarabayashi. More generally, we show that this holds in the setting of multi-commodity 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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
الصفحات495-504
عدد الصفحات10
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2013
الحدث45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, الولايات المتّحدة
المدة: ١ يونيو ٢٠١٣٤ يونيو ٢٠١٣

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing
رقم المعيار الدولي للدوريات (المطبوع)0737-8017

!!Conference

!!Conference45th Annual ACM Symposium on Theory of Computing, STOC 2013
الدولة/الإقليمالولايات المتّحدة
المدينةPalo Alto, CA
المدة١/٠٦/١٣٤/٠٦/١٣

قم بذكر هذا