अधिकतम प्रवाह समस्या के प्रकार के लिए जटिलता \ संदर्भ अनुरोध

Question

चाप क्षमताओं के साथ मानक अधिकतम लागत प्रवाह समस्या में, चाप का उपयोग करने की लागत चाप के माध्यम से प्रवाह के लिए आनुपातिक होती है। उदाहरण के लिए, यदि$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)$इसके बजाय: \ start {case} \ mathbf {c} _ {uv} f_ {uv} + \ mathbf {b} _ {uv}, \ text {if} f_ {uv}> 0, \\ 0, \ पाठ {अन्यथा} \ अंत {मामलों} जहां$\mathbf{b}_{uv}$ कुछ पूर्वनिर्धारित धनात्मक संख्या है।

1. क्या अधिकतम प्रवाह समस्या का प्रकार एक बहुपद-समय समाधान मानता है?
2. यदि नहीं, तो क्या कोई संदर्भ हैं जो आप मुझे इंगित कर सकते हैं?

PS मुझे पता है कि मेरे द्वारा बताए गए संस्करण को MILP के रूप में आसानी से पेश किया जा सकता है, हालांकि, मुझे इस समस्या के संरचनात्मक परिणामों और जटिलता के बारे में जानने में दिलचस्पी है।

Answer 1

मुझे लगता है, कि वहाँ भी एक इष्टतम समाधान मौजूद नहीं है।

इसे रखने की इच्छा है $\epsilon$-सभी लागत एकत्र करने के लिए हर किनारे पर बहें $b_{uv}$। दूसरी ओर आप किनारों पर अधिकतम लागत के साथ प्रवाह को अधिकतम करना चाहते हैं$c_{uv}$। इससे दबाव पड़ता है$\epsilon$ जितना संभव हो उतना छोटा, जबकि अभी भी $\epsilon > 0$। इस तरह के एक$\epsilon$ मौजूद नहीं हो सकता।