Второй самый маленький

13

Что-нибудь известно о втором наименьшем - -резе в сети потока? Или, в общем, об этой проблеме:sT

Вход: сеть и число , все в двоичном виде. Выход: наименьшее - вырезать.NК
КsT

- й наименьший - разреза любые - вырезать, например , что существует ровно - порезы , чьи мощностиКsT(S,T)sTК-1 sT

  • попарно разные и
  • действительно меньше, чем емкость .(S,T)

Я хотел бы знать, как это может быть вычислено и может ли это быть сделано эффективно как для случая .Кзнак равно1

Оливер Витт
источник
Вы можете найти второй наименьший срез, добавив веса ко всем ребрам наименьшего среза, а затем вычислив новый наименьший срез. Это, вероятно, работает до тех пор, пока k закодировано в унарном порядке (и, конечно, для константы k ) εКК
Юваль Фильмус
2
Я не понимаю, как это помогает. Представьте себе сеть путей, состоящую из трех узлов , v , t только с двумя ребрами ( s , v ) и ( v , t ) . Далее, пусть емкости будут c ( s , v ) = 1 и c ( v , t ) = 2 . Понятно, что минимальные срезы ( s , v ) и вторые самые маленькие срезы ( v ,svt(s,v)(v,t)c(s,v)=1c(v,t)=2(s,v) . Увеличение производительности, как вы описали, снова даст ( s , v ) минимальное сокращение с производительностью 1 + ϵ . Как я могу вывести второй самый маленький вырез из этого? (v,t)(s,v)1+ϵ
Оливер Витт
Добавление нижней границы на колпачок среза является линейным неравенством, просто добавьте на один эпсилон больше, чем колпачок min, и запустите LP. Вы можете повторить это k раз, чтобы получить то, что вы хотите. Это, вероятно, может быть изменено как модификация в сети, но я не разработал это.
Каве
Я вижу, как это работает, если в унарной кодировке. Что, если это двоичный файл? В этом случае модификация сети не может быть выполнена за k итераций. kk
Оливер Витт
1
Я сомневаюсь, что есть простое решение, если k является двоичным. Мы можем проверить, есть ли срез крышки c, как я описал. Мне кажется, что, по сути, подсчет количества возможных c может быть связан с подсчетом количества совпадений и, возможно, # P-complete. (Это только моя интуиция, а не аргумент.)
Каве

Ответы:

7

Второй наименьший срез, а в более общем случае наименьших срезов, может быть найден во временном полиноме от k и размера сети. Видеть:kk

HW Hamacher. алгоритм для нахождения K лучшие сокращения сети. Опер. Местожительство Lett. 1 (5): 186–189, 1982, doi: 10.1016 / 0167-6377 (82) 90037-2 .(Kn4)k

HW Hamacher, J.-C. Пикард и М. Кейранн. Нахождение лучших сокращений в сети. Опер. Местожительство Lett. 2 (6): 303-305, 1984, doi: 10.1016 / 0167-6377 (84) 90083-X .K

HW Hamacher и M. Queyranne. лучшим решениям комбинаторных задач оптимизации. Энн. Опер. Местожительство 4 (1–4): 123–143, 1985, doi: 10.1007 / BF02022039 .K

Дэвид Эппштейн
источник
Разве они не позволяют равные веса среди лучших ? Кажется, вопрос задается о k-м наименьшем весе , который, как предполагает Каве, пахнет больше как проблема # P-complete. kk
Андраш Саламон
Я тоже так понимаю: равные веса разрешены. Кажется, это не отвечает на вопрос. Тем не менее, я не знал об этих бумагах, спасибо за это.
Оливер Уитт
1
Вопрос плохо сформулирован, потому что он запрашивает одну вещь ( й наименьший разрез), а затем добавляет ограничение, которое превращает вопрос во что-то другое ( k- й наименьший различимый вес среза). Я согласен с тем, что версия этой проблемы с весомым весом, вероятно, будет $ P-полной. kk
Дэвид Эппштейн