Сложность \ Запрос справки по варианту задачи о максимальном расходе

Aug 18 2020

В стандартной задаче максимальной стоимости потока с мощностью дуги стоимость использования дуги пропорциональна потоку через дугу. Например, если$f_{uv}$ поток через дугу $(u,v)$, то стоимость использования этой дуги определяется выражением $\mathbf{c}_{uv} f_{uv}$, где $\mathbf{c}_{uv}$- некоторое предопределенное действительное число. Итак, цель, в достижении которой мы заинтересованы, -$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, где $E$- ребра в графе. Вы можете предположить, что граф содержит узел источника и приемный узел, и все потоки исходят из источника и стекают в узел приемника.

Рассмотрим вариант, при котором затраты на использование дуги $(u,v)$вместо этого задается: \ begin {cases} \ mathbf {c} _ {uv} f_ {uv} + \ mathbf {b} _ {uv}, \ text {if} f_ {uv}> 0, \\ 0, \ text {иначе} \ end {cases} где$\mathbf{b}_{uv}$ - некоторое заранее определенное положительное число.

  1. Допускает ли вариант задачи о максимальном потоке решение за полиномиальное время?
  2. Если нет, то есть ли ссылки, на которые вы можете указать мне?

PS Я знаю, что изложенный мною вариант можно легко представить как MILP, однако мне интересно узнать о структурных результатах и ​​сложности этой проблемы.

Ответы

4 Luke599999 Aug 18 2020 at 14:07

Я бы предположил, что оптимального решения даже не существует.

Ты хочешь иметь $\epsilon$-поток через все края, чтобы собрать всю стоимость $b_{uv}$. С другой стороны, вы хотите максимизировать поток по краям с максимальной стоимостью.$c_{uv}$. Это приводит к необходимости$\epsilon$ как можно меньше, пока еще $\epsilon > 0$. Такой$\epsilon$ не может существовать.