पुरस्कार-इकट्ठा करने वाला वन उपमोड्यूलर दंड के साथ: सुधारित अनुमान

प्रतिबंधित वन समस्याएँ ग्राफ़ समस्याओं का एक वर्ग形成 करती हैं जहाँ ग्राफ़ के भीतर कुछ कटौती के लिए विशिष्ट कनेक्टिविटी आवश्यकताओं को न्यूनतम लागत वाली किनारों के सेट का चयन करके संतुष्ट करना होता है। इन समस्याओं का पुरस्कार-इकट्ठा करने वाला संस्करण उन अनुपालन आवश्यकताओं को अनदेखा करने के लिए दंड देने की अनुमति देकर लचीलापन पेश करता है। गोमन्स और विलियमसन ने एक सामान्य तकनीक पेश की और प्रतिबंधित वन समस्याओं के लिए एक 2-अनुमान एल्गोरिदम विकसित किया। इसके आगे, शर्मा, स्वामी, और विलियमसन ने इन समस्याओं के पुरस्कार-इकट्ठा करने वाले संस्करण के लिए 2.54-अनुमान एल्गोरिदम विकसित करके इस काम का विस्तार किया। उनके ढांचे की सामान्यता से प्रेरित होकर, जिसमें स्टाइनर ट्री, स्टाइनर वनों और उनके रूपांतर शामिल हैं, हमने आगे की खोज की। हम इस सामान्य मॉडल के लिए 2-अनुमान एल्गोरिदम प्राप्त करके एक महत्वपूर्ण सुधार प्रस्तुत करते हैं, जो प्रतिबंधित वन समस्याओं के अनुमान कारक के बराबर है।