คำขอ Complexity \ Reference สำหรับตัวแปรของปัญหาการไหลสูงสุด
ในปัญหาการไหลของต้นทุนสูงสุดมาตรฐานที่มีความสามารถในการโค้งต้นทุนของการใช้ส่วนโค้งจะเป็นสัดส่วนกับการไหลผ่านส่วนโค้ง ตัวอย่างเช่นถ้า$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}$ คือจำนวนบวกที่กำหนดไว้ล่วงหน้า
- ตัวแปรของปัญหาการไหลสูงสุดยอมรับวิธีแก้ปัญหาพหุนามเวลาหรือไม่
- ถ้าไม่มีมีข้อมูลอ้างอิงที่คุณสามารถชี้ให้ฉันดูได้ไหม
ป.ล. ฉันรู้ว่าตัวแปรที่ฉันระบุนั้นสามารถถูกจัดให้เป็น MILP ได้อย่างง่ายดายอย่างไรก็ตามฉันสนใจที่จะเรียนรู้เกี่ยวกับผลลัพธ์เชิงโครงสร้างและความซับซ้อนของปัญหานี้
คำตอบ
ฉันคิดว่าไม่มีแม้แต่วิธีแก้ปัญหาที่ดีที่สุด
คุณต้องการที่จะมี $\epsilon$- ไหลผ่านทุกขอบเพื่อรวบรวมต้นทุนทั้งหมด $b_{uv}$. ในทางกลับกันคุณต้องการเพิ่มการไหลข้ามขอบด้วยต้นทุนสูงสุด$c_{uv}$. สิ่งนี้นำไปสู่ความกดดันที่จะมี$\epsilon$ ให้เล็กที่สุดในขณะที่ยังอยู่ $\epsilon > 0$. เช่น$\epsilon$ ไม่สามารถดำรงอยู่ได้