पॉलीनोमियल टाइम अप्रॉक्सिमेशन स्कीम (PTAS)
NP-कम्प्लीट समस्याओं जैसे 0-1 नैपसैक समस्या या सबसेट सम समस्या के लिए हम कुछ पॉलीनोमियल टाइम समाधान खोज सकते हैं। ये समस्याएं वास्तविक दुनिया में बहुत लोकप्रिय हैं, इसलिए इन्हें संभालने के कुछ तरीके होने चाहिए।
पॉलीनोमियल टाइम अप्रॉक्सिमेशन स्कीम (PTAS) ऑप्टिमाइज़ेशन समस्याओं के लिए एल्गोरिदम को अनुमानित करने का एक प्रकार है। 0-1 नैपसैक समस्या के लिए एक स्यूडो-पॉलीनोमियल समाधान मौजूद है, लेकिन जब मान बड़े होते हैं, तो वह समाधान व्यवहार्य नहीं होता। तब हमें PTAS समाधान की आवश्यकता होती है।
ग्राफ कलरिंग, K-सेंटर समस्या आदि जैसी कुछ NP-कम्प्लीट समस्याओं का कोई ज्ञात पॉलीनोमियल टाइम समाधान नहीं है। PTAS एल्गोरिदम को अनुमानित करने के लिए उपयोग किया जाता है। ये एल्गोरिदम एक पैरामीटर ε > 0 लेते हैं और अनुमान लगाने के लिए हम (1 + ε) को न्यूनतम करते हैं और (1 - ε) को अधिकतम करते हैं।
उदाहरण
उदाहरण के लिए, यदि हम एक न्यूनतमीकरण समस्या चुनते हैं और ε = 0.5 लेते हैं, तो PTAS का उपयोग करके समाधान लगभग 1.5 होगा। इसलिए रनिंग टाइम n के संदर्भ में पॉलीनोमियल होनी चाहिए, लेकिन यह ε के संदर्भ में एक्सपोनेंशियल हो सकती है।
