複雑さ\最大フロー問題のバリアントの参照要求
アーク容量を伴う標準的な最大コストフロー問題では、アークを使用するコストはアークを通る流れに比例します。たとえば、$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} where$\mathbf{b}_{uv}$ 事前定義された正の数です。
- 最大フロー問題の変形は、多項式時間の解を認めますか？
- そうでない場合、私に指摘できる参考資料はありますか？
PS私が述べたバリアントは、MILPとして簡単に提示できることを知っていますが、この問題の構造的な結果と複雑さについて学ぶことに興味があります。
回答
最適な解決策すら存在しないと思います。
あなたがしたい $\epsilon$-すべてのコストを収集するためにすべてのエッジを流れる $b_{uv}$。一方、最も高いコストでエッジを横切るフローを最大化する必要があります$c_{uv}$。これは持っている圧力につながります$\epsilon$ できるだけ小さく、それでも $\epsilon > 0$。そのような$\epsilon$ 存在することはできません。