Известно, что Форд-Фулкерсон или Эдмондс-Карп с эвристикой толстой трубы (два алгоритма для максимального потока) не должны останавливаться, если некоторые веса нерациональны. На самом деле они могут даже сходиться на неправильном значении! Однако во всех примерах, которые я мог найти в литературе [ссылки ниже, плюс ссылки в них], используется только одно иррациональное значение: сопряженное золотое сечение и другие значения, которые либо рациональны, либо рациональны, кратны . Мой главный вопрос:
Общий вопрос: что происходит с другими иррациональными ценностями?
Например (но не думаю, что вы должны отвечать на все эти вопросы, чтобы опубликовать их - я бы нашел интересный ответ на любой из них или на другие вопросы, которые подпадают под приведенный выше общий вопрос)
При наличии любого , можно ли построить (или даже показать существование) такие контрпримеры?
Более слабо: известны ли примеры, в которых используется иррациональное значение, существенно отличающееся от? То есть есть ли который не является рациональным кратным (или более сильно не в ) и такие, что существуют контрпримеры к Форду-Фулкерсону и / или Эдмондсу-Карпу, где лежат все веса ?
В другом направлении, существует ли иррациональное такой, что Форд-Фулкерсон (соответственно, Эдмондс-Карп) останавливается с правильным значением на всех графиках , вес которых все из? (Или более сильно, из?)
Во всех случаях я хочу предположить что-то похожее на реальную модель ОЗУ, чтобы точные арифметические и точные сравнения действительных чисел выполнялись в постоянное время.
(Существуют другие алгоритмы с максимальным потоком, которые, как известно, выполняются за строго полиномиальное время, даже с произвольными действительными весами, и, возможно, поэтому этот тип вопроса, возможно, не был дополнительно исследован. Но только что я учил эти алгоритмы в моем классе алгоритмов старшекурсников Мне все еще интересно об этом.)
Ссылки
Минимальный контрпример для Ford-Fulkerson был дан Zwick TCS 1999
Контрпример для Эдмондса-Карпа был дан Queyranne или Queyranne Math. Опер. Местожительство 1980 , хотя я не знаю, является ли это минимальным.
И то, и другое можно найти в примечаниях к лекциям Джеффа Эриксона , причем первое - в разделе 23.5, а второе - в упражнении 14 лекции 23.
источник