Ini adalah pertanyaan yang agak subyektif. Saya tertarik mempelajari literatur tentang hasil multikommoditas aliran-potong, terutama hasil 'positif' yang menunjukkan bahwa aliran adalah perkiraan yang baik untuk memotong (katakanlah, dalam faktor yang konstan atau polylogaritmik dalam jumlah aliran). Contohnya adalah:
1) Aliran polytope (juga disebut polytope permintaan) untuk aliran multikomoditas dalam grafik yang tidak diarahkan berada dalam O (log k) dari pemotongan seperti yang ditunjukkan pada
F. Leighton dan S. Rao, "Sebuah teorema min-cut max-flow perkiraan maksimum untuk masalah aliran multikommoditas yang seragam dengan aplikasi untuk algoritma aproksimasi," di Proc. Simposium Tahunan ke-28 tentang Yayasan Ilmu Komputer, (Los Alamitos, California), 1988.
N. Linial, E. London, dan Y. Rabinovich, "Geometri grafik dan beberapa aplikasi algoritmiknya," Combinatorica, vol. 15, tidak. 2, hlm. 215–245, 1995.
2) Permintaan polytope dari aliran multikomoditas dalam grafik berarah dengan tuntutan simetris berada dalam O (log ^ 2 k) dari pemotongan seperti yang ditunjukkan pada
P. Klein, S. Plotkin, S. Rao, dan E. Tardos, "Terikat pada rasio min-cut max-flow untuk aliran multikomoditas terarah," J. Algoritma, no. 22, hlm. 241–269, 1997.
3) Tingkat jumlah maksimum dalam siaran grup berada dalam faktor 2 dari multicut. (Saya tidak tahu referensi untuk hasil ini. Bisakah seseorang membantu saya dengan ini? Terima kasih.)
Saya ingin tahu lebih banyak hasil positif seperti itu yang menegaskan aliran mendekati pemotongan dengan asumsi struktur masalah tertentu (seperti tidak terarahnya grafik atau tuntutan simetris, seperti di atas). Akan lebih bagus jika Anda bisa memberi saya ringkasan satu-baris dari hasil dan referensi dari makalah ini. Terima kasih.
sumber