Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями

Рисунок 6. Алгоритм FBB для примера на рис. 5 для значений r = 1/2, <math>\epsilon \;</math> = 0,15 и единичного веса каждой вершины. Алгоритм завершает работу после нахождения разреза <math>(X_2, \bar{X_2}) \;</math>.

Таблица 1. Сравнение алгоритмов SN, PFM3 и FBB (r = 1/2, <math>\epsilon \;</math> = 0,1)

Таблица 2. Сравнение алгоритмов EIG1, PB и FBB (r = 1/2, <math>\epsilon \;</math> = 0,1). Все допускают отклонение <math>\le 10%</math>

'''Теорема 3. Количество итераций и финальный размер сетевого разреза представляют собой невозрастающие функции от <math>\epsilon \;</math>.'''

На практике алгоритм FBB завершается намного быстрее, чем указывает временная сложность для наихудшего случая, как показано в разделе «Экспериментальные результаты». Теорема 3 позволяет повысить эффективность FBB и качество разбиения для больших значений <math>\epsilon \;</math>. Это неверно для других подходов к разбиению – таких как эвристика K&L.