Karmaşıklık \ Maksimum akış sorununun varyantı için referans talebi

Question

Ark kapasiteleri ile standart maksimum maliyet akışı probleminde, bir ark kullanmanın maliyeti ark boyunca akışla orantılıdır. Örneğin, eğer$f_{uv}$ ark boyunca akış $(u,v)$, daha sonra bu yayı kullanmanın maliyeti şu şekilde verilir: $\mathbf{c}_{uv} f_{uv}$, nerede $\mathbf{c}_{uv}$önceden tanımlanmış bir gerçek sayıdır. Dolayısıyla, maksimize etmekle ilgilendiğimiz hedef,$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, nerede $E$grafikteki kenarlardır. Grafiğin bir kaynak ve bir havuz düğümü içerdiğini ve tüm akışların kaynaktan yayıldığını ve havuz düğümüne aktığını varsayabilirsiniz.

Ark kullanımıyla ilişkili maliyetin hangi varyantta olduğunu düşünün $(u,v)$bunun yerine: \ begin {case} \ mathbf {c} _ {uv} f_ {uv} + \ mathbf {b} _ {uv}, \ text {if} f_ {uv}> 0, \\ 0, \ text {aksi halde} \ end {case} nerede$\mathbf{b}_{uv}$ önceden tanımlanmış bir pozitif sayıdır.

1. Maksimum akış probleminin varyantı bir polinom zamanlı çözümü kabul ediyor mu?
2. Değilse, bana işaret edebileceğiniz referanslar var mı?

Not: Belirtmiş olduğum varyantın bir MILP olarak kolayca ortaya konulabileceğini biliyorum, ancak bu sorunun yapısal sonuçlarını ve karmaşıklığını öğrenmekle ilgileniyorum.

Answer 1

Optimal bir çözüm bile olmadığını varsayıyorum.

Sahip olmak istiyorsun $\epsilon$-tüm maliyeti toplamak için her uçtan akış $b_{uv}$. Öte yandan, en yüksek maliyetle kenarlar boyunca akışı en üst düzeye çıkarmak istiyorsunuz$c_{uv}$. Bu, sahip olmak için baskıya yol açar$\epsilon$ mümkün olduğu kadar küçükken $\epsilon > 0$. Bu tür bir$\epsilon$ var olamaz.