يك الگوريتم نيوتن گسسته براي مسأله ممانعت از كمترين st-برش

مسأله كمترين st-برش يكي از مشهورترين مسايل بهينه‌سازي است كه فصل مشترك دسته مسايل برنامه‌ريزي خطي، بهينه‌سازي شبكه و بهينه‌سازي تركيبياتي است. جدا از اين كه اين مسأله، دوگان مسأله معروف بيشترين جريان بوده و از لحاظ نظري اهميت دارد، از منظر كاربرد نيز بسيار مورد توجه محققين قرار گرفته است. در اين مقاله يك توسيع از اين مسأله را در قالب نظريه بازيها بررسي مي‌كنيم. مسأله مورد نظر را ممانعت از كمترين st-برش مي‌ناميم. مسأله داراي دو بازيكن مهاجم و مدافع است. مهاجم سعي در انفصال خطوط مواصلاتي بين دو نقطه را با انتخاب كمترين برش داشته و مدافع با استحكام بخشي اين خطوط مي‌خواهد جلوي عملكرد مهاجم را تا حد ممكن بگيرد. در اين مقاله، يك الگوريتم زمان چندجمله‌اي براي حل مسأله پيشنهاد مي‌شود. اين الگوريتم از روش ريشه‌يابي نيوتن-كاتس استفاده كرده و در تعداد متناهي تكرار جواب دقيق مسأله را مي‌يابد.