एक तेज़ 3-आसन्नता सीमित पेड़ आवरण समस्या के लिए जो किनारे पर लोड के साथ है

किनारे के लोड के साथ सीमित पेड़ आवरण समस्या पेड़ आवरण समस्या का एक प्रकार है, जहां हमें सुविधा उद्घाटन लागत, किनारे की लागत और लोड, साथ ही शीर्ष के लोड दिए जाते हैं। हम एक न्यूनतम लागत का पेड़ आवरण खोजने की कोशिश करते हैं ताकि प्रत्येक पेड़ का कुल किनारे और शीर्ष लोड दिए गए सीमा से अधिक न हो। इस समस्या के लिए हमने O (m n) समय का 3-आसन्नता एल्गोरिदम प्रस्तुत किया है। यह एक निश्चित LP रूपांतरण से शुरू करके प्राप्त किया जाता है। हम एक संयोजनात्मक एल्गोरिदम देते हैं जो O (m n) समय में LP को सबसे अच्छा हल करता है। फिर, हम दिखाते हैं कि एक रेखीय समय गोलाई और विभाजन तकनीक एक संपूर्ण समाधान के लिए नेतृत्व करती है जो LP समाधान की तुलना में अधिकतम 3 गुना लागत रखती है। अंत में, हम साबित करते हैं कि LP का संपूर्णता अंतर 3 है, जो दर्शाता है कि हम सामान्य रूप से गोलाई चरण को सुधार नहीं सकते।