पूर्ण बहुपद-काल सन्निकटन प्रणाली: Difference between revisions

From Vigyanwiki
(minor changes)
(Work done)
Line 1: Line 1:
एक पूरी तरह से पॉलिनोमियल-समय आपकर्षण योजना (FPTAS) एक [[कलन विधि|ऐल्गोरिथ्म]] होता है जिसका उद्देश्य संवाद समस्याओं, विशेषकर [[अनुकूलन समस्या|अनुकुलन समस्याओं]], के आपूर्तिकरण समाधान के आस-पास समाधान खोजना होता है। FPTAS को प्रॉब्लम की एक इंस्टेंस और पैरामीटर ε > 0 के रूप में इनपुट मिलता है। यह सही मान की कम से कम <math>1-\epsilon</math> गुना और अधिकतम <math>1 + \epsilon</math> गुना की मान देता है, जो कि सही मान से होते हैं।
'''पूर्ण बहुपद-काल सन्संवृतन प्रणाली''' (फुल्ली पॉलिनोमियल-टाइम अप्प्रोक्सिमशन स्कीम, '''एफपीटीएएस''') एक [[कलन विधि|ऐल्गोरिथ्म]] होता है जिसका उद्देश्य फंक्शन समस्याओं, विशेषकर [[अनुकूलन समस्या|इष्टमीकरण समस्याओं]], के आपूर्तिकरण हल के आस-पास हल ज्ञात करना होता है। एफपीटीएएस को समस्या का एक दृष्टांत और पैरामीटर ε > 0 के रूप में इनपुट प्राप्त होता है। यह यथार्थ मान (वैल्यू) का कम से कम <math>1-\epsilon</math> गुना और अधिकतम <math>1 + \epsilon</math> गुना देता है, जो कि यथार्थ मान से होते हैं।


अनुकूलन समस्याओं के संदर्भ में, सही मान को विकल्प समाधान की मान के रूप में समझा जाता है, और यह अक्सर इस संदर्भ में समझा जाता है कि एक FPTAS को एक वैध समाधान प्रस्तुत करना चाहिए (और केवल समाधान की मान नहीं)। एक मान प्रस्तुत करना और उस मान के साथ एक समाधान प्राप्त करना उस समस्या की [[स्वयं कम करने की क्षमता|स्व-पुनर्निर्धारणीयता]] का अभिवादन करते हुए समान होते हैं।
इष्टमीकरण समस्याओं के संदर्भ में, यथार्थ मान को विकल्प समाधान के मान के रूप में समझा जाता है, और यह प्रायः इस संदर्भ में समझा जाता है कि एफपीटीएएस को एक मान्य समाधान प्रस्तुत करना चाहिए (और केवल समाधान का मान नहीं)। एक मान प्रस्तुत करना और उस मान के साथ समाधान प्राप्त करना उस समस्या की [[स्वयं कम करने की क्षमता|स्व-पुनर्निर्धारणीयता]] का अभिवादन करते हुए समान होते हैं।


महत्वपूर्ण बात यह है कि एक FPTAS का रनटाइम समस्या के आकार और 1/ε में पॉलिनोमियल होता है। यह एक सामान्य [[बहुपद-समय सन्निकटन योजना|पॉलिनोमियल-समय आपकर्षण योजना]] (PTAS) के विपरीत है। एक सामान्य PTAS का रनटाइम हर विशिष्ट ε के लिए समस्या के आकार में पॉलिनोमियल होता है, लेकिन 1/ε में विश्वसनीयता के साथ विस्तारणशील हो सकता है।<ref>G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. ''Complexity and Approximation: Combinatorial optimization problems and their approximability properties'', Springer-Verlag, 1999.</ref>
महत्वपूर्ण यह है कि एफपीटीएएस के रनटाइम समस्या के आकार और 1/ε में बहुपद होता है। यह एक सामान्य [[बहुपद-समय सन्निकटन योजना|बहुपद-काल सन्संवृतन प्रणाली]] (पॉलिनोमियल-टाइम अप्प्रोक्सिमशन स्कीम, पीटीएएस) के विपरीत है। सामान्य PTAS का रन-टाइम प्रत्येक विशिष्ट ε के लिए समस्या आकार में बहुपद है, लेकिन 1/ε में घातांकीय हो सकता है।<ref>G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. ''Complexity and Approximation: Combinatorial optimization problems and their approximability properties'', Springer-Verlag, 1999.</ref>


FPTAS शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक FPTAS हो। FPTAS PTAS की एक उपसमूह है, और जब तक P = NP नहीं हो, यह एक सख्त उपसमूह है।<ref name="Jansen3">{{citation|last=Jansen|first=Thomas|title=Lectures on Proof Verification and Approximation Algorithms|pages=5–28|year=1998|editor1-last=Mayr|editor1-first=Ernst W.|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|publisher=Springer|doi=10.1007/BFb0053011|isbn=9783540642015|editor2-last=Prömel|editor2-first=Hans Jürgen|editor3-last=Steger|editor3-first=Angelika|editor3-link=Angelika Steger}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p.&nbsp;20].</ref>
एफपीटीएएस शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक एफपीटीएएस हो। एफपीटीएएस पीटीएएस की एक उपसमुच्चय है, और जब तक P = NP नहीं हो, यह एक सख्त उपसमुच्चय है।<ref name="Jansen3">{{citation|last=Jansen|first=Thomas|title=Lectures on Proof Verification and Approximation Algorithms|pages=5–28|year=1998|editor1-last=Mayr|editor1-first=Ernst W.|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|publisher=Springer|doi=10.1007/BFb0053011|isbn=9783540642015|editor2-last=Prömel|editor2-first=Hans Jürgen|editor3-last=Steger|editor3-first=Angelika|editor3-link=Angelika Steger}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p.&nbsp;20].</ref>
== अन्य जटिलता वर्गों से संबंध ==
== अन्य कम्प्लेक्सिटी वर्गों से संबंध ==
FPTAS में सभी समस्याएँ मानक पैरामीटरीकरण के संदर्भ में निश्चित पैरामीटर संवाद्य हैं।<ref>{{Cite journal |last1=Cai |first1=Liming |last2=Chen |first2=Jianer |date=June 1997 |title=फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर|journal=Journal of Computer and System Sciences |language=en |volume=54 |issue=3 |pages=465–474 |doi=10.1006/jcss.1997.1490|doi-access=free }}</ref>
एफपीटीएएस में सभी समस्याएं मानक पैरामीटरीकरण के संबंध में निश्चित-पैरामीटर पर आधारित हैं।<ref>{{Cite journal |last1=Cai |first1=Liming |last2=Chen |first2=Jianer |date=June 1997 |title=फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर|journal=Journal of Computer and System Sciences |language=en |volume=54 |issue=3 |pages=465–474 |doi=10.1006/jcss.1997.1490|doi-access=free }}</ref>


किसी भी पॉलिनोमियल बाउंडेड उद्देश्य कार्य के साथ कोई भी [[दृढ़ता से एनपी-पूर्ण|मजबूत NP-कठिन]] अनुकुलन समस्या FPTAS नहीं हो सकता, जब तक P=NP नहीं हो।<ref name="vvv">{{cite book|last=Vazirani|first=Vijay V.|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2003|isbn=3-540-65367-8|location=Berlin|pages=294–295}}</ref> हालांकि, उलटी बात नहीं सिद्ध होती: उदाहरण स्वरूपन, यदि P NP से बराबर नहीं है, तो डोरा में दो प्रतिबंधों के साथ यह स्थिरता मजबूत NP-कठिन नहीं है, लेकिन जब तक आदर्श उद्देश्य पॉलिनोमियल बाउंडेड नहीं हो, तो उसका कोई FPTAS नहीं है।<ref>{{cite book|title=बस्ता समस्याएँ|publisher=Springer|year=2004|author1=H. Kellerer |author2=U. Pferschy |author3=D. Pisinger }}</ref>
बहुपद से परिबद्ध (बाउंडेड) उद्देश्य फलन के साथ किसी भी [[दृढ़ता से एनपी-पूर्ण|दृढ़ NP-हार्ड]] अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि P=NP नहीं।<ref name="vvv">{{cite book|last=Vazirani|first=Vijay V.|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2003|isbn=3-540-65367-8|location=Berlin|pages=294–295}}</ref> हालाँकि, प्रतिवर्ती नहीं होता: उदाहरण स्वरूपन, यदि P, NP से बराबर नहीं है, तो डोरा में दो प्रतिबंधों के साथ यह स्थिरता दृढ़ NP-हार्ड नहीं है, लेकिन जब तक इष्टतम उद्देश्य बहुपद परिबद्ध नहीं हो, तो उसका कोई एफपीटीएएस नहीं है।<ref>{{cite book|title=बस्ता समस्याएँ|publisher=Springer|year=2004|author1=H. Kellerer |author2=U. Pferschy |author3=D. Pisinger }}</ref>


== एक गतिशील प्रोग्राम को एफपीटीएएस में परिवर्तित करना ==
== डायनामिक प्रोग्राम को एफपीटीएएस में परिवर्तित करना ==
वेगिंगर<ref name=":0">{{Cite journal|last=Woeginger|first=Gerhard J.|date=2000-02-01|title=When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901|journal=INFORMS Journal on Computing|volume=12|issue=1|pages=57–74|doi=10.1287/ijoc.12.1.57.11901|issn=1091-9856}}</ref> ने एक ऐसे विशेष श्रेणी के [[गतिशील प्रोग्रामिंग]] को एक FPTAS में बदलने के लिए एक सामान्य योजना प्रस्तुत की।
वेगिंगर<ref name=":0">{{Cite journal|last=Woeginger|first=Gerhard J.|date=2000-02-01|title=When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901|journal=INFORMS Journal on Computing|volume=12|issue=1|pages=57–74|doi=10.1287/ijoc.12.1.57.11901|issn=1091-9856}}</ref> ने एक ऐसे विशेष श्रेणी के [[गतिशील प्रोग्रामिंग|डायनामिक प्रोग्रामिंग]] को एक एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की।


=== इनपुट ===
=== इनपुट ===
यह योजना उन अनुकुलन समस्याओं को संभालती है जिनमें इनपुट निम्नलिखित तरीके से परिभाषित होता है:
यह योजना उन इष्टमीकरण समस्याओं को हैंडल करती है जिनमें इनपुट निम्नलिखित तरीके से परिभाषित होता है:
*इनपुट n वेक्टरों, x1, ..., xn से बना होता है।
*इनपुट ''n'' सदिशों, ''x''<sub>1</sub>,...,''x<sub>n</sub>'' से बना होता है।
* प्रत्येक इनपुट वेक्टर किसी <math>a</math> गैर-नकारात्मक पूर्णांकों से बना होता है, जहाँ <math>a</math> इनपुट पर निर्भर कर सकता है।
* प्रत्येक इनपुट सदिश किसी <math>a</math> गैर-नकारात्मक पूर्णांकों से बना होता है, जहाँ <math>a</math> इनपुट पर निर्भर कर सकता है।
* इनपुट वेक्टरों के सभी घटक बाइनरी में एनकोड होते हैं। इसलिए समस्या का आकार O(n+log(X)) होता है, जहाँ X सभी वेक्टरों के सभी घटकों की योग है।
* इनपुट सदिशों के सभी घटक बाइनरी में एनकोड होते हैं। इसलिए समस्या का आकार O(''n''+log(''X'')) होता है, जहाँ ''X'' सभी सदिशों के सभी घटकों की योग है।


=== अत्यंत सरल गतिशील कार्यक्रम ===
=== अत्यंत सरल डायनामिक प्रोग्राम ===
माना जाता है कि समस्या में एक गतिशील-प्रोग्रामिंग (DP) एल्गोरिथ्म होता है जो स्थितियों का उपयोग करता है। प्रत्येक स्थिति एक ऐसा वेक्टर होता है जिसमें कुछ <math>b</math> गैर-नकारात्मक पूर्णांक होते हैं, जहाँ <math>b</math> इनपुट से अनबद्ध होता है। DP n कदमों में काम करता है। प्रत्येक कदम i पर, यह इनपुट xi को प्रोसेस करता है और स्थितियों का एक सेट Si बनाता है। प्रत्येक स्थिति एक अधिंश समस्या को एनकोड करती है, x1, ..., xi का उपयोग करके। DP के घटक हैं:
माना जाता है कि समस्या में एक डायनामिक-प्रोग्रामिंग (डीपी) एल्गोरिथ्म होता है जो स्थितियों का उपयोग करता है। प्रत्येक स्थिति एक ऐसा सदिश होता है जिसमें कुछ <math>b</math> गैर-नकारात्मक पूर्णांक होते हैं, जहाँ <math>b</math> इनपुट से अनबद्ध होता है। डीपी ''n'' चरणों में काम करता है। प्रत्येक चरण ''i'' पर, यह इनपुट ''x<sub>i</sub>'' को प्रोसेस करता है और स्थितियों का एक समुच्चय ''S<sub>i</sub>'' बनाता है। प्रत्येक स्थिति एक अधिंश समस्या को एनकोड करती है, ''x''<sub>1</sub>,...,''x<sub>i</sub>'' का उपयोग करके। डीपी के घटक हैं:


* एक प्रारंभिक स्थितियों का सेट S0।
* एक ''प्रारंभिक स्थितियों'' का समुच्चय ''S''<sub>0</sub> ।
* संक्रमण समारोहों का सेट F। प्रत्येक समारोह f F में एक जोड़ी (स्थिति, इनपुट) को एक नई स्थिति में मान देता है।
* ''परिवर्ती फलन'' का समुच्चय ''F''। प्रत्येक फलन ''f,'' ''F'' में एक युग्म (स्थिति, इनपुट) को एक नई स्थिति में मान देता है।
* एक उद्देश्य समारोह g, जो स्थिति को उसके मूल्य में मान देता है।
* एक उद्देश्य फलन g, जो स्थिति को उसके मूल्य में मान देता है।


डीपी का एल्गोरिदम है:
डीपी का एल्गोरिदम है:


* चलो एस<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय.
* मान लीजिए ''S''<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय।
* k = 1 से n के लिए करें:
* k = 1 से n के लिए करें:
** चलो एस<sub>k</sub>:= {f(s,x<sub>k</sub>) | एफ में एफ, एस में एस<sub>k</sub><sub>−1</sub>}
** समुच्चय ''S<sub>k</sub>'' := {''f''(''s'',''x<sub>k</sub>'') | ''f'' in ''F'', ''s'' in ''S<sub>k</sub>''<sub>−1</sub>}
* आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस<sub>n</sub>}.
* आउटपुट न्यूनतम/अधिकतम {g(s) | s in ''S<sub>n</sub>''}
डायनैमिक प्रोग्रामिंग का रनटाइम संभावित स्थितियों की संख्या में लीनियर होता है। सामान्यत: इस संख्या का आकार इनपुट समस्या के आकार में विस्तारणशील हो सकता है: यह O(n V^b) में हो सकता है, जहाँ V एक स्थिति में प्रकट होने वाले सबसे बड़े पूर्णांक है। अगर V O(X) में है, तो रनटाइम O(n X^b) में होता है, जो कि केवल प्यूडो-पॉलिनोमियल समय होता है, क्योंकि यह समस्या के आकार में विस्तारणशील होता है जो O(log X) में होता है।
डायनैमिक प्रोग्रामिंग का रनटाइम संभावित स्थितियों की संख्या में लीनियर होता है। सामान्यत: इस संख्या का आकार इनपुट समस्या के आकार में घातांकीय हो सकता है: यह O(''n V<sup>b</sup>'') में हो सकता है, जहाँ ''V'' एक स्थिति में प्रकट होने वाले सबसे बड़े पूर्णांक है। यदि ''V,'' O(''X'') में है, तो रनटाइम O(''n X<sup>b</sup>'') में होता है, जो कि केवल प्यूडो-बहुपद समय होता है, क्योंकि यह समस्या के आकार में घातांकीय  होता है जो O(log ''X'') में होता है।


इसे पॉलिनोमियल बनाने का एक तरीका है स्थिति-स्थान को काट देना: प्रत्येक कदम में संभावित स्थितियों को सब नहीं रखने की जगह, केवल स्थितियों का एक सबसेट रखने की जगह; उन स्थितियों को हटा दें जो अन्य स्थितियों के "पर्याप्त नजदीक" हैं। निश्चित स्थितियों की यह कट कुछ शर्तों के तहत की जा सकती है, जिनके तहत यह किसी स्थिति की उच्चता मान में बहुत अधिक बदलाव नहीं लाता है।
इसे बहुपद बनाने का एक तरीका है ''स्थिति-स्थान को ट्रिम'' करें: प्रत्येक चरण में संभावित स्थितियों को सब नहीं रखने की जगह, केवल स्थितियों का एक उपसमुच्चय रखने की जगह; उन स्थितियों को हटा दें जो अन्य स्थितियों के "''पर्याप्त रूप से संवृत''" हैं। निश्चित स्थितियों की यह कट कुछ शर्तों के अधीन की जा सकती है, जिनके अधीन यह किसी स्थिति की उच्चता मान में बहुत अधिक बदलाव नहीं लाता है।


इसे औपचारिकत: इसे हम मानते हैं कि समस्या के पास एक गैर-नकारात्मक पूर्णांक वेक्टर d = (d1, ..., db) है, जिसे समस्या का डिग्री वेक्टर कहा जाता है। हर वास्तविक संख्या r > 1 के लिए, हम कहते हैं कि दो स्थिति-वेक्टर s1, s2 (d, r)-नजदीक हैं अगर, प्रत्येक समन्वय j, 1 से b तक: <math>r^{-d_j} \cdot s_{1,j} \leq s_{2,j} \leq r^{d_j} \cdot s_{1,j}</math> (विशेषकर, अगर किसी j के लिए dj = 0 है, तो <math>s_{1,j} = s_{2,j}</math>)।
इसे औपचारिकत: इसे हम मानते हैं कि समस्या के पास एक गैर-नकारात्मक पूर्णांक सदिश ''d'' = (''d''<sub>1</sub>,...,''d<sub>b</sub>'') है, जिसे समस्या का डिग्री सदिश कहा जाता है। प्रत्येक वास्तविक संख्या ''r''>1 के लिए, हम कहते हैं कि दो स्थिति-सदिश ''s''<sub>1</sub>,''s''<sub>2</sub> ''(d,r)''-संवृत हैं यदि, प्रत्येक समन्वय ''j'', 1,...,''b'' तक: <math>r^{-d_j} \cdot s_{1,j} \leq s_{2,j} \leq r^{d_j} \cdot s_{1,j}</math> (विशेषकर, यदि किसी ''j'' के लिए ''d<sub>j</sub>''=0 है, तो <math>s_{1,j} = s_{2,j}</math>)।


कोई समस्या अत्यंत कल्याणकारी कहलाती है यदि वह निम्नलिखित तीन शर्तों को पूरा करती हो:
कोई समस्या अत्यंत कल्याणकारी कहलाती है यदि वह निम्नलिखित तीन शर्तों को पूरा करती हो:


# निकटता संक्रिया-समारोह द्वारा संरक्षित है: किसी भी r>1 के लिए, किसी भी संक्रमण समारोह f F में, किसी भी इनपुट-वेक्टर x के लिए, और किसी भी दो स्थिति-वेक्टरों s1, s2 के लिए, निम्नलिखित सत्य है: अगर s1 s2 के लिए (d, r)-नजदीक है, तो f(s1, x) f(s2, x) के लिए (d, r)-नजदीक है।
# ''परिवर्ती फलन द्वारा सामीप्यता (प्रॉक्सिमिटी) संरक्षित रहती है'': किसी भी ''r''>1 के लिए, किसी भी संक्रमण फलन ''f,'' ''F'' में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिशों ''s''<sub>1</sub>,''s''<sub>2</sub> के लिए, निम्नलिखित सत्य है: यदि ''s''<sub>1</sub> ''s''<sub>2</sub> के लिए (d, r)-संवृत है, तो ''f(s<sub>1</sub>, x) f(s<sub>2</sub>, x)'' के लिए (d, r)-संवृत है।
#*इसके लिए एक पर्याप्त शर्त को निम्नलिखित रूप में जांचा जा सकता है। हर फ़ंक्शन f(s, x) F में, और हर कोआर्डिनेट j, 1 से b तक, f की jवीं कोआर्डिनेट को fj(s, x) के रूप में दर्शाया जा सकता है। यह fj को b+a चरणों में एक पूर्णांक फ़ंक्शन के रूप में देखा जा सकता है। मान लीजिए कि हर ऐसे fj एक ऐसा पॉलिनोमियल है जिसमें गैर-नकारात्मक संख्यात्मक हैं। इसे z में एकल पूर्णांक के पॉलिनोमियल में बदलें, s=(zd1,...,zdb) और x=(1,...,1) को विकल्प करके। यदि परिणामक पॉलिनोमियल का डिग्री z में अधिक से अधिक dj है, तो शर्त 1 पूरी होती है।
#*इसके लिए एक पर्याप्त शर्त को निम्नलिखित रूप में जांचा जा सकता है। प्रत्येक फलन ''f(s, x),'' ''F'' में, और प्रत्येक निर्देशांक ''j'', 1,...,''b'' तक, ''f'' की ''j''वीं निर्देशांक को ''f<sub>j</sub>''(s,x) के रूप में दर्शाया जा सकता है। यह ''f<sub>j</sub>'' को ''b+a'' चरणों में एक पूर्णांक फलन के रूप में देखा जा सकता है। मान लीजिए कि प्रत्येक ऐसे ''f<sub>j</sub>'' एक ऐसा बहुपद है जिसमें गैर-नकारात्मक संख्यात्मक हैं। इसे z में एकल पूर्णांक के बहुपद में बदलें, ''s''=(z<sup>d1</sup>,...,z<sup>db</sup>) और ''x=(1,...,1)'' को विकल्प करके। यदि परिणामक बहुपद का डिग्री ''z'' में अधिक से अधिक ''d<sub>j</sub>'' है, तो शर्त 1 पूरी होती है।
#मूल्य समारोह द्वारा निकटता का संरक्षित रहना: एक पूर्णांक G ≥ 0 मौजूद है (जो मूल्य समारोह g और डिग्री वेक्टर d का एक समारोह है), ऐसा कि किसी भी r>1, और किसी भी दो स्थिति-वेक्टरों s1, s2 के लिए, निम्नलिखित सत्य है: अगर s1 s2 के लिए (d, r)-नजदीक है, तो: g(s1) ≤ rG · g(s2) (कमीकरण समस्याओं में); g(s1) ≥ r(-G) · g(s2) (अधिकतमीकरण समस्याओं में)।
#मूल्य फलन द्वारा संवृत का संरक्षित रहना: एक पूर्णांक G ≥ 0 मौजूद है (जो मूल्य फलन g और डिग्री सदिश d का एक फलन है), ऐसा कि किसी भी r>1, और किसी भी दो स्थिति-सदिशों ''s''<sub>1</sub>,''s''<sub>2</sub> के लिए, निम्नलिखित सत्य है: यदि ''s''<sub>1</sub> ''s''<sub>2</sub> के लिए ''(d, r)''-संवृत है, तो: ''g''(''s''<sub>1</sub>) ≤ ''r<sup>G</sup>'' · ''g''(''s<sub>2</sub>'') (न्यूनीकरण समस्याओं में); ''g''(''s''<sub>1</sub>) ≥ ''r<sup>(-G)</sup>'' · ''g''(''s<sub>2</sub>'') (अधिकतमीकरण समस्याओं में)।
#*इसके लिए पर्याप्त शर्त यह है कि फ़ंक्शन g एक पॉलिनोमियल फ़ंक्शन (b चरणों की) हो, जिसमें गैर-नकारात्मक संख्यात्मक हों।
#*इसके लिए पर्याप्त शर्त यह है कि फलन ''g'' एक बहुपद फलन (''b'' वेरिएबल की) हो, जिसमें गैर-नकारात्मक संख्यात्मक हों।
#तकनीकी शर्तें:
#तकनीकी शर्तें:
#*सभी संक्रमण समारोह f F और मूल्य समारोह g को पॉलिटाइम में मूल्यांकित किया जा सकता है।
#*सभी संक्रमण फलन ''f, F'' और मूल्य फलन g को पॉलिटाइम में मूल्यांकित किया जा सकता है।
#*संक्रमण समारोहों की संख्या |F| n और log(X) में पॉलिनोमियल है।
#*परिवर्ती फलन की संख्या |''F''|, ''n'' और log(''X'') में बहुपद है।
#*प्रारंभिक स्थितियों का सेट S0 को n और log(X) में पॉलिनोमियल समय में गणना की जा सकती है।
#*प्रारंभिक स्थितियों का समुच्चय ''S''<sub>0</sub> को ''n'' और log(''X'') में बहुपद समय में गणना की जा सकती है।
#*Vj को स्थिति के कोआर्डिनेट j में प्रकट होने वाले सभी मानों का सेट कहें। तब, Vj में हर मान का [[प्राकृतिक|ln]] न केवल एक पॉलिनोमियल P1(n,log(X)) में सबसे अधिक है।
#*''V<sub>j</sub>'' को स्थिति के निर्देशांक ''j'' में प्रकट होने वाले सभी मानों का समुच्चय कहें। तब, ''V<sub>j</sub>'' में प्रत्येक मान का [[प्राकृतिक|ln]] न केवल एक बहुपद P<sub>1</sub>(n,log(X)) में सबसे अधिक है।
#*अगर dj=0, तो Vj की कार्डिनैलिटी न केवल एक पॉलिनोमियल P2(n,log(X)) में सबसे अधिक हो सकती है।
#*यदि ''d<sub>j</sub>''=0, तो Vj की कार्डिनैलिटी न केवल एक बहुपद P<sub>2</sub>(n,log(X)) में सबसे अधिक हो सकती है।
हर अत्यधिक दयालु समस्या के लिए, गतिशील कार्यक्रम को एक FPTAS में परिवर्तित किया जा सकता है। निर्धारित करें:
प्रत्येक अत्यधिक बेनिवॉलेंट समस्या के लिए, डायनामिक कार्यक्रम को एक एफपीटीएएस में परिवर्तित किया जा सकता है। निर्धारित करें:


* <math>\epsilon</math> := आवश्यक सन्निकटन अनुपात।
* <math>\epsilon</math>:= आवश्यक सन्संवृतन अनुपात।
* <math>r := 1 + \frac{\epsilon}{2 G n}</math>, जहां G स्थिति 2 से स्थिरांक है। ध्यान दें <math>\frac{1}{\ln{r}}  \leq 1 + \frac{2Gn}{\epsilon}</math>.
* <math>r := 1 + \frac{\epsilon}{2 G n}</math>, जहां ''G'' स्थिति 2 से स्थिरांक है। ध्यान दें <math>\frac{1}{\ln{r}}  \leq 1 + \frac{2Gn}{\epsilon}</math>.
* <math>L := \left\lceil \frac{P_1(n,\log(X))}{\ln(r)} \right\rceil</math>, जहाँ P1 स्थिति 3 से बहुपद है (प्रत्येक मान के ln पर एक ऊपरी सीमा जो एक राज्य वेक्टर में दिखाई दे सकती है)। ध्यान दें कि <math>L\leq \left\lceil \left(1 + \frac{2 G n}{\epsilon}\right) P_1(n, \log{X}) \right\rceil</math>, इसलिए यह इनपुट के आकार में और <math>1/\epsilon</math> में बहुपद है। साथ ही, <math>r^L = e^{\ln{r}}\cdot L \geq e^{P_1(n,\log{x})}</math>, इसलिए पी1 की परिभाषा के अनुसार, प्रत्येक पूर्णांक जो एक राज्य-वेक्टर में दिखाई दे सकता है वह सीमा [0,आरएएल] में है।
* <math>L := \left\lceil \frac{P_1(n,\log(X))}{\ln(r)} \right\rceil</math>, जहाँ P<sub>1</sub> स्थिति 3 से बहुपद है (प्रत्येक मान के ln पर ऊपरी सीमा जो एक स्थिति सदिश में दिखाई दे सकती है)। ध्यान दें कि <math>L\leq \left\lceil \left(1 + \frac{2 G n}{\epsilon}\right) P_1(n, \log{X}) \right\rceil</math>, इसलिए यह इनपुट के आकार में और <math>1/\epsilon</math> में बहुपद है। साथ ही, <math>r^L = e^{\ln{r}}\cdot L \geq e^{P_1(n,\log{x})}</math>, इसलिए P<sub>1</sub> की परिभाषा के अनुसार, प्रत्येक पूर्णांक जो एक स्थिति-सदिश में दिखाई दे सकता है वह सीमा [0,''r<sup>L</sup>''] में है।
* सीमा [0, rL] को L+1 r-अंतरालों में विभाजित करें: <math>I_0 = [0]; I_1 = [1,r); I_2 = [r,r^2); \ldots ; I_L = [r^{L-1}, r^L]</math>।
* सीमा [0,''r<sup>L</sup>''] को ''L''+1 ''r''-अंतरालों में विभाजित करें: <math>I_0 = [0]; I_1 = [1,r); I_2 = [r,r^2); \ldots ; I_L = [r^{L-1}, r^L]</math>।
* स्थिति अंतरिक्ष को r-बॉक्स में विभाजित करें: प्रत्येक निर्देशिका k जिसका डिग्री dk ≥ 1 है, विशीर्णता ऊपर L+1 अंतरालों में विभाजित किया जाता है; प्रत्येक निर्देशिका जिसका dk = 0 है, P2(n,log(X)) एकल अंतरालों में विभाजित किया जाता है - प्रत्येक संभावित मूल्य के लिए एक अंतराल (जहाँ P2 condition 3 का पॉलिनोमियल है)।
* स्थिति समष्टि को ''r''-बॉक्स में विभाजित करें: प्रत्येक निर्देशिका ''k'' जिसका डिग्री ''d<sub>k</sub>'' ≥ 1 है, विशीर्णता ऊपर ''L''+1 अंतरालों में विभाजित किया जाता है; प्रत्येक निर्देशिका जिसका ''d<sub>k</sub>'' = 0 है, P<sub>2</sub>(n,log(X)) एकल अंतरालों में विभाजित किया जाता है - प्रत्येक संभावित मूल्य के लिए एक अंतराल (जहां P<sub>2</sub> उपरोक्त शर्त 3 से बहुपद है)।
**ध्यान दें कि प्रत्येक संभावित स्थिति केवल एक r-बॉक्स में शामिल है; अगर दो स्थितियाँ एक ही r-बॉक्स में हैं, तो वे (d,r)-नजदीक हैं।
**ध्यान दें कि प्रत्येक संभावित स्थिति केवल ''r''-बॉक्स में सम्मिलित है; यदि दो स्थितियाँ एक ही r-बॉक्स में हैं, तो वे ''(d,r)''-संवृत हैं।
*<math>R := (L + 1 + P_2(n,\log{X}))^b</math>.
*<math>R := (L + 1 + P_2(n,\log{X}))^b</math>.
** ध्यान दें कि r-बॉक्स की संख्या अधिकतम R है। क्योंकि b एक निश्चित स्थिर संख्या है, इसलिए यह R इनपुट के आकार में पॉलिनोमियल और <math>1/\epsilon</math> में है।
** ध्यान दें कि ''r''-बॉक्स की संख्या अधिकतम ''R'' है। क्योंकि ''b'' एक निश्चित स्थिर संख्या है, इसलिए यह ''R'' इनपुट के आकार में बहुपद और <math>1/\epsilon</math> में है।


FPTAS DP के समान ढंग से चलता है, लेकिन प्रत्येक कदम में, यह स्थिति सेट को एक छोटे सेट Tk में काटता है, जो प्रत्येक r-बॉक्स में एक ही स्थिति को शामिल करता है। FPTAS की एल्गोरिथम निम्नलिखित है:
एफपीटीएएस डीपी के समान ढंग से चलता है, लेकिन प्रत्येक चरण में, यह स्थिति समुच्चय को एक छोटे समुच्चय ''T<sub>k</sub>'' में काटता है, जो प्रत्येक r-बॉक्स में एक ही स्थिति को सम्मिलित करता है। एफपीटीएएस की एल्गोरिथम निम्नलिखित है:
* मान लीजिए T0 := S0 = प्रारंभिक अवस्थाओं का समुच्चय।
* मान लीजिए ''T''<sub>0</sub>  := ''S''<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय।
* k = 1 से n के लिए करें:
* ''k'' = 1 से ''n'' के लिए करें:
** चलो यू<sub>k</sub>:= {f(s,x<sub>k</sub>) | एफ में एफ, टी में एस<sub>k</sub><sub>−1</sub>}
** मान लीजिए ''U<sub>k</sub>'' := {''f''(''s'',''x<sub>k</sub>'') | ''f'' in ''F'', ''s'' in ''T<sub>k</sub>''<sub>−1</sub>}
**मान लीजिए टी<sub>k</sub>:= यू की एक छंटनी प्रति<sub>k</sub>: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं<sub>k</sub>, T में बिल्कुल एक अवस्था रखें<sub>k</sub>.
**मान लीजिए ''T<sub>k</sub>'' := ''U<sub>k</sub>'' की एक संक्षिप्त प्रति: प्रत्येक r-बॉक्स के लिए जिसमें ''U<sub>k</sub>'' के एक या अधिक राज्य हैं, ''T<sub>k</sub>'' में ठीक एक स्थिति रखें।
* आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस<sub>n</sub>}.
* आउटपुट न्यूनतम/अधिकतम {g(s) | s in ''T<sub>n</sub>''}
FPTAS का रनटाइम प्रत्येक Ti में संभावित स्थितियों की कुल संख्या में पॉलिनोमियल होता है, जो अधिकतम एकत्रित r-बॉक्स की कुल संख्या होती है, जो अधिकतम R होती है, जो पॉलिनोमियल होती है n, log(X), और <math>1/\epsilon</math> में।
एफपीटीएएस का रनटाइम प्रत्येक ''T<sub>i</sub>'' में संभावित स्थितियों की कुल संख्या में बहुपद होता है, जो अधिकतम एकत्रित r-बॉक्स की कुल संख्या होती है, जो अधिकतम ''R'' होती है, जो बहुपद होती है ''n'', log(''X''), और <math>1/\epsilon</math> में।


ध्यान दें कि प्रत्येक स्थिति su में Uk में, उसका उपसमूह Tk में कम से कम एक स्थिति st होता है जो su के (d, r)-नजदीक होता है। भी, प्रत्येक Uk प्रारंभिक (बिना काटे गए) DP के स्थिति सेट Sk की एक उपसेट है। FPTAS की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:<ref name=":0" />{{Rp|page=|location=Lem.3.3}}  
ध्यान दें कि प्रत्येक स्थिति ''s<sub>u</sub>'' में ''U<sub>k</sub>'' में, उसका उपसमुच्चय ''T<sub>k</sub>'' में कम से कम एक स्थिति ''s<sub>t</sub>'' होता है जो su के (d, r)-संवृत होता है। भी, प्रत्येक ''U<sub>k</sub>'' प्रारंभिक (बिना काटे गए) डीपी के स्थिति समुच्चय ''S<sub>k</sub>'' की एक उपसमुच्चय है। एफपीटीएएस की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:<ref name=":0" />{{Rp|page=|location=Lem.3.3}}  


प्रत्येक कदम k में 0,...,n, प्रत्येक स्थिति ss Sk में, एक ऐसी स्थिति st होती है जो ss के (d,rk)-नजदीक होती है।
प्रत्येक चरण k में 0,...,n, प्रत्येक स्थिति ''s<sub>s</sub>'' ''S<sub>k</sub>'' में, एक ऐसी स्थिति ''s<sub>t</sub>'' होती है जो ''s<sub>s</sub>'' के (d,rk)-संवृत होती है।


इसका प्रमाण k पर प्रेरण द्वारा है। k=0 के लिए हमारे पास Tk=Sk है; प्रत्येक अवस्था (d,1)-स्वयं के निकट है। मान लीजिए कि लेम्मा k-1 के लिए धारण करता है। Sk में प्रत्येक अवस्था ss के लिए, ss- को Sk-1 में अपने पूर्ववर्तियों में से एक होने दें, ताकि f(ss−,x)=ss। प्रेरण धारणा के अनुसार, Tk-1 में एक अवस्था st- है, यानी (d,rk-1)-ss− के करीब। चूंकि निकटता संक्रमणों (उपरोक्त शर्त 1) द्वारा संरक्षित है, f(st−,x) (d,rk-1)-f(ss−,x)=ss के करीब है। यह f(st−,x) यूके में है। ट्रिमिंग के बाद, Tk में एक अवस्था st होती है जो कि (d,r)-f(st-,x) के करीब होती है। यह सेंट (डी,आरके)-एसएस के करीब है।
इसका प्रमाण k पर प्रेरण द्वारा है। k=0 के लिए हमारे पास ''T<sub>k</sub>''=''S<sub>k</sub>'' है; प्रत्येक अवस्था (d,1)-स्वयं के संवृत है। मान लीजिए कि लेम्मा k-1 के लिए धारण करता है। ''S<sub>k</sub>'' में प्रत्येक अवस्था ''s<sub>s</sub>'' के लिए, ''s<sub>s</sub>''- को ''S<sub>k</sub>''-1 में अपने पूर्ववर्तियों में से एक होने दें, ताकि f(''s<sub>s</sub>''−,x)=''s<sub>s</sub>''। प्रेरण धारणा के अनुसार, ''T<sub>k</sub>''-1 में एक अवस्था ''s<sub>t</sub>'' - है, अर्थात (d,rk-1)-''s<sub>s</sub>''− के संवृत। चूंकि संवृत संक्रमणों (उपरोक्त शर्त 1) द्वारा संरक्षित है, ''f(s<sub>t</sub>−,x) (d,rk-1)-f(s<sub>s</sub>−,x)=s<sub>s</sub>'' के संवृत है। यह f(''s<sub>t</sub>''−,x) यूके में है। ट्रिमिंग के बाद, ''T<sub>k</sub>'' में एक अवस्था ''s<sub>t</sub>'' होती है जो कि ''(d,r)-f(s<sub>t</sub>-,x)'' के संवृत होती है। यह सेंट (''d'',''r<sup>k</sup>'')-''s<sub>s</sub>'' के संवृत है।


अब विचार करें कि स्थिति s* Sn में है, जो सर्वोत्तम समाधान का संवादना करती है (यानी, g(s*)=OPT)। उपरोक्त उपनिवेश के अनुसार, एक स्थिति t* Tn में है, जो s* के (d,rn)-नजदीक है। निकटता मूल्य समारोह द्वारा संरक्षित होती है, इसलिए एक अधिकतमीकरण समस्या के लिए g(t*) ≥ r(-Gn) · g(s*) होता है। r की परिभाषा द्वारा, <math>r^{-Gn}\geq (1-\epsilon)</math>। इस प्रकार <math>g(t^*)\geq (1-\epsilon)\cdot OPT</math> होता है। एक समान तर्क एक कमीकरण समस्या के लिए काम करता है।
अब विचार करें कि स्थिति ''s''*, ''S<sub>n</sub>'' में है, जो सर्वोत्तम समाधान का संवादना करती है (अर्थात, ''g''(''s*'')=OPT)। उपरोक्त उपनिवेश के अनुसार, एक स्थिति ''t''*, ''T<sub>n</sub>'' में है, जो ''s''* के (''d'',''r<sup>n</sup>'')-संवृत है। संवृत मूल्य फलन द्वारा संरक्षित होती है, इसलिए एक अधिकतमीकरण समस्या के लिए ''g''(t*) ≥ ''r<sup>(-Gn)</sup>'' · ''g''(''s*'') होता है। r की परिभाषा द्वारा, <math>r^{-Gn}\geq (1-\epsilon)</math>। इस प्रकार <math>g(t^*)\geq (1-\epsilon)\cdot OPT</math> होता है। एक समान तर्क एक न्यूनीकरण समस्या के लिए काम करता है।


==== उदाहरण ====
==== उदाहरण ====
यहां अत्यंत-परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार FPTAS है।<ref name=":0" />
यहां अत्यंत-बेनिवॉलेंट समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।<ref name=":0" />


1. [[मल्टीवे संख्या विभाजन|अनेकगुणा संख्या संविभाजन]] ([[समान-मशीन शेड्यूलिंग]] के साथ व्यक्तिगत करने की अभिलाषा के साथ) जिसका लक्ष्य सबसे बड़ी योग को कम करना है, बेहद दयालु है। यहां, हमारा a = 1 होता है (इंटीज होते हैं), और b = बिनों की संख्या (जिसे स्थिर माना जाता है)। प्रत्येक स्थिति b योगों की बिनों के योगों का प्रतिनिधित्व करने वाले b पूर्णांकों का एक वेक्टर होती है। यहाँ b की फ़ंक्शन होती हैं: प्रत्येक फ़ंक्शन j अगले इंटीज को बिन j में डालने का प्रतिनिधित्व करती है। फ़ंक्शन g(s) s के सबसे बड़े तत्व को चुनती है। S0 = {(0,...,0)}। दयालुता के शर्त d=(1,...,1) और G=1 के साथ पूरी होती है। यह परिणाम [[वर्दी-मशीन शेड्यूलिंग|समान मशीन अनुसूची]] और असंबद्ध मशीन अनुसूची में विस्तार पाता है जब मशीनों की संख्या स्थिर होती है (यह इसलिए आवश्यक है क्योंकि R - r-बॉक्सों की अधिकतम संख्या - b में घनात्मक होती है)। Pm||<math>\max C_j</math> या Qm||<math>\max C_j</math> या Rm||<math>\max C_j</math> कहा जाता है।
1. [[मल्टीवे संख्या विभाजन|मल्टीवे संख्या संविभाजन]] ([[समान-मशीन शेड्यूलिंग]] के साथ व्यक्तिगत करने की अभिलाषा के साथ) जिसका लक्ष्य सबसे बड़ी योग को कम करना है, बेहद बेनिवॉलेंट है। यहां, हमारा ''a'' = 1 होता है (इंटीज होते हैं), और ''b'' = बिनों की संख्या (जिसे स्थिर माना जाता है)। प्रत्येक स्थिति ''b'' योगों की बिनों के योगों का प्रतिनिधित्व करने वाले ''b'' पूर्णांकों का एक सदिश होती है। यहाँ ''b'' की फलन होती हैं: प्रत्येक फलन j अगले इंटीज को बिन ''j'' में डालने का प्रतिनिधित्व करती है। फलन ''g(s), s'' के सबसे बड़े तत्व को चुनती है। ''S<sub>0</sub> = {(0,...,0)}''बेनिवॉलेंट के शर्त ''d=(1,...,1)'' और ''G''=1 के साथ पूरी होती है। यह परिणाम [[वर्दी-मशीन शेड्यूलिंग|समान मशीन अनुसूची]] और असंबद्ध मशीन अनुसूची में विस्तार पाता है जब मशीनों की संख्या स्थिर होती है (यह इसलिए आवश्यक है क्योंकि ''R'' - ''r''-बॉक्सों की अधिकतम संख्या - ''b'' में घनात्मक होती है)। Pm||<math>\max C_j</math> या Qm||<math>\max C_j</math> या Rm||<math>\max C_j</math> कहा जाता है।


* ध्यान दें: एक विशेष प्रकार की स्थिति b=2 को विचार करें, जहाँ लक्ष्य दो भागों के योग के बीच अंतर के वर्ग को कम करना है। एक ही DP का उपयोग किया जा सकता है, लेकिन इस बार मूल्य समारोह g(s) = (s1-s2)2 के साथ, जहाँ s1 और s2 दो भागों के योग होते हैं। अब, शर्त 2 का उल्लंघन होता है: स्थितियाँ (s1,s1) और (s1,s2) (d,r)-नजदीक हो सकती हैं, लेकिन g(s1,s1) = 0 होता है जबकि g(s1,s2) > 0 होता है। इस प्रकार, उपरोक्त सिद्धांत का लागू नहीं हो सकता है। यद्यपि, समस्या के पास FPTAS नहीं होता है जब तक P=NP नहीं होता है, क्योंकि FPTAS का पॉलिटाइम में उपयोग करके निर्णय किया जा सकता है कि श्रेष्ठ मूल्य 0 है या नहीं।
* ध्यान दें: एक विशेष प्रकार की स्थिति ''b''=2 को विचार करें, जहाँ लक्ष्य दो भागों के योग के ''बीच अंतर के वर्ग'' को कम करना है। एक ही डीपी का उपयोग किया जा सकता है, लेकिन इस बार मूल्य फलन ''g''(''s'') = (''s''<sub>1</sub>-''s''<sub>2</sub>)<sup>2</sup> के साथ, जहाँ ''s''<sub>1</sub> और ''s''<sub>2</sub> दो भागों के योग होते हैं। अब, शर्त 2 का उल्लंघन होता है: स्थितियाँ (''s<sub>1</sub>'',''s<sub>1</sub>'') और (''s<sub>1</sub>'',''s''<sub>2</sub>) (d,r)-संवृत हो सकती हैं, लेकिन ''g(s<sub>1</sub>,s<sub>1</sub>)'' = 0 होता है जबकि ''g(s<sub>1</sub>,s<sub>2</sub>)'' > 0 होता है। इस प्रकार, उपरोक्त सिद्धांत का लागू नहीं हो सकता है। यद्यपि, समस्या के पास एफपीटीएएस नहीं होता है जब तक P=NP नहीं होता है, क्योंकि एफपीटीएएस का पॉलिटाइम में उपयोग करके निर्णय किया जा सकता है कि श्रेष्ठ मूल्य 0 है या नहीं।


2. समान या समान मशीनों की किसी भी निश्चित संख्या पर घन कार्य पूरा होने के समय का योग - Qm||<math>\sum C_j^3</math> द्वारा निरूपित बाद वाला - a=1, b=3, d=(1,1,3) के साथ पूर्व-परोपकारी है। इसे पूर्ण होने के समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।
2. समान या समान मशीनों की किसी भी निश्चित संख्या पर घन कार्य पूरा होने के समय का योग - Qm||<math>\sum C_j^3</math> द्वारा निरूपित बाद वाला - ''a''=1, ''b''=3, ''d''=(1,1,3) के साथ पूर्व-बेनिवॉलेंट है। इसे पूर्ण होने के समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।


3. समान या समान मशीनों की किसी भी निश्चित संख्या पर भारित समापन समय का योग - बाद वाले को Qm||<math>\sum w_j C_j</math> द्वारा दर्शाया गया है।
3. समान या समान मशीनों की किसी भी निश्चित संख्या पर भारित समापन समय का योग - बाद वाले को Qm||<math>\sum w_j C_j</math> द्वारा दर्शाया गया है।
Line 91: Line 91:
4. समय-निर्भर प्रसंस्करण समय के साथ, समान या समान मशीनों की किसी भी निश्चित संख्या पर पूरा होने के समय का योग: Qm|time-dep|<math>\sum C_j</math>। यह पूरा होने के समय के भारित योग के लिए भी लागू है।
4. समय-निर्भर प्रसंस्करण समय के साथ, समान या समान मशीनों की किसी भी निश्चित संख्या पर पूरा होने के समय का योग: Qm|time-dep|<math>\sum C_j</math>। यह पूरा होने के समय के भारित योग के लिए भी लागू है।


5. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: एम||<math>\sum w_j|C_j|</math>।
5. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: m||<math>\sum w_j|C_j|</math>।


=== सरल गतिशील कार्यक्रम ===
=== सरल डायनामिक कार्यक्रम ===


सरल गतिशील प्रोग्राम उपरोक्त फॉर्मूलेशन में निम्नलिखित घटक जोड़ते हैं:
सरल डायनामिक प्रोग्राम उपरोक्त फॉर्मूलेशन में निम्नलिखित घटक जोड़ते हैं:


* एक फ़िल्टरिंग फ़ंक्शनों का सेट H, जो F की तरही संख्या में होते हैं। प्रत्येक फ़ंक्शन hi H में एक जोड़ (स्थिति, इनपुट) को एक बूलियन मूल्य में चित्रित करती है। मूल्य "सत्य" तभी होना चाहिए जब और केवल जब इस जोड़ पर fi का संक्रमण किया जाएगा और यह एक मान्य स्थिति तक पहुँचाएगा।
* एक ''फ़िल्टरिंग फलनों'' का समुच्चय ''H'', जो ''F'' की तरही संख्या में होते हैं। प्रत्येक फलन ''h<sub>i,</sub>'' ''H'' में एक युग्म (स्थिति, इनपुट) को एक बूलियन मूल्य में चित्रित करती है। मूल्य "सत्य" तभी होना चाहिए जब और केवल जब इस जोड़ पर ''f<sub>i</sub>'' का संक्रमण किया जाएगा और यह एक मान्य स्थिति तक पहुँचाएगा।
*एक प्रदर्शन संबंध, जो स्थितियों पर एक [[आंशिक आदेश]] है (कोई समानता नहीं, सभी जोड़ों का तुलना किया नहीं जा सकता है), और एक अर्ध-प्रदर्शन संबंध, जो स्थितियों पर एक पूर्ण पूर्व-क्रम है (समानताएँ अनुमति दी जाती हैं, सभी जोड़ों की तुलना की जा सकती है)।
*एक ''प्रदर्शन संबंध'', जो स्थितियों पर एक [[आंशिक आदेश]] है (कोई समानता नहीं, सभी जोड़ों का तुलना किया नहीं जा सकता है), और एक अर्ध-प्रदर्शन संबंध, जो स्थितियों पर एक पूर्ण पूर्व-क्रम है (समानताएँ अनुमति दी जाती हैं, सभी जोड़ों की तुलना की जा सकती है)।
मूल डीपी को इस प्रकार संशोधित किया गया है:
मूल डीपी को इस प्रकार संशोधित किया गया है:
*चलिए एस<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय.
*मान लीजिए ''S''<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय।
* k = 1 से n के लिए करें:
*k = 1 से n के लिए करें:
** चलो एस<sub>k</sub> := {एफ<sub>j</sub>(एस,एक्स<sub>k</sub>) | एफ<sub>j</sub>एफ में, एस में एस<sub>k</sub><sub>−1</sub>, ''एच<sub>j</sub>(एस,एक्स<sub>k</sub>)=सत्य' }, जहां h<sub>j</sub>संक्रमण फ़ंक्शन f के अनुरूप फ़िल्टर फ़ंक्शन है<sub>j</sub>.
**मान लीजिए S<sub>k</sub> := {''f<sub>j</sub>''(''s'',''x<sub>k</sub>'') | ''f<sub>j</sub>'' in ''F'', ''s'' in ''S<sub>k</sub>''<sub>−1</sub>, '''''h<sub>j</sub>''(''s'',''x<sub>k</sub>'')=True''' }, जहां ''h''<sub>j</sub> ट्रांज़िशन फलन ''f<sub>j</sub>'' के अनुरूप फ़िल्टर फलन है।
* आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस<sub>n</sub>}.
* आउटपुट का न्यूनतम/अधिकतम {g(s) | s in ''S<sub>n</sub>''}
किसी समस्या को 'परोपकारी' कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो उपरोक्त शर्तों 1, 2, 3 का विस्तार करती है):
एक समस्या को '''बेनिवॉलेंट''' कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो ऊपर दी गई शर्तों 1, 2, 3 को विस्तारित करती हैं):


# निकटता को संक्रमण कार्यों द्वारा संरक्षित किया जाता है: किसी भी r>1 के लिए, F में किसी भी संक्रमण फ़ंक्शन f के लिए, किसी भी इनपुट-वेक्टर x के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है:
# ''प्राक्षिपत्ति परियोजनाओं द्वारा संरक्षित की जाती है'': किसी भी ''r''>1 के लिए, किसी भी परियोजना फलन ''f,'' ''F'' में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिश ''s''<sub>1</sub>,''s''<sub>2</sub> के लिए, निम्नलिखित सत्य है:
#* यदि ''s''<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>,'' और एस<sub>1</sub> अर्ध-प्रभुत्व एस<sub>2</sub>'', फिर या तो () ''एफ''(''एस''<sub>1</sub>,x) (d,r)-f(s) के करीब है<sub>2</sub>,x), और f(s<sub>1</sub>,x) अर्ध-प्रभावी f(s)।<sub>2</sub>,x)', या (बी) एफ(एस)।<sub>1</sub>,x) f(s) पर हावी है<sub>2</sub>,एक्स)
#* यदि '''''s''<sub>1,</sub> ''s''<sub>2</sub> के प्रति ''(d,r)''-संवृत''' '''है, ''s''<sub>1,</sub> ''s''<sub>2</sub> को क्वासी-डॉमिनेट''' '''करता है''', तो या तो (a) '''''f(s<sub>1</sub>,x)'' ''f(s<sub>2</sub>,x)'' के प्रति ''(d,r)''-संवृत है, और ''f(s<sub>1</sub>,x) f(s<sub>2</sub>,x)'' को क्वासी-डॉमिनेट करता है''', या (b) ''f(s<sub>1</sub>,x) f(s<sub>2</sub>,x)'' को डॉमिनेट करता है।
#* यदि एस<sub>1</sub> एस पर हावी है<sub>2</sub>, फिर f(s<sub>1</sub>,x) f(s) पर हावी है<sub>2</sub>,एक्स)
#* यदि ''s''<sub>1</sub> ''s''<sub>2</sub> को डॉमिनेट करता है, तो ''f(s<sub>1</sub>,x) f(s<sub>2</sub>,x)'' को डॉमिनेट करता है।
# निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है: एक पूर्णांक G ≥ 0 (मान फ़ंक्शन g और डिग्री वेक्टर d का एक फ़ंक्शन) मौजूद है, जैसे कि किसी भी r>1 के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है:
# ''मूल्य फलन द्वारा प्राक्षिपत्ति संरक्षित की जाती है'': एक पूर्णांक ''G'' ≥ 0 (मान फलन ''g'' और डिग्री सदिश ''d'' का एक फलन) विद्यमान है, जैसे कि किसी भी ''r''>1 के लिए, और किसी भी दो स्थिति-सदिश ''s''<sub>1</sub>,''s''<sub>2</sub> के लिए, निम्नलिखित धारण करता है:
#* यदि ''s''<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>, और एस<sub>1</sub> अर्ध-प्रभुत्व एस<sub>2</sub>''<nowiki/>'','' फिर: ''g''(''s''<sub>1</sub>) ≤ आर<sup>जी</sup> · जी(एस<sub>2</sub>) (समस्याओं को न्यूनतम करने में); जी(एस<sub>1</sub>) ≥ आर<sup>(-G)</sup> · g(s<sub>2</sub>) (अधिकतमीकरण समस्याओं में)।
#* यदि '''''s''<sub>1</sub> ''s''<sub>2</sub> के प्रति ''(d,r)''-संवृत है, और ''s''<sub>1</sub> ''s''<sub>2</sub> को क्वासी-ड'''''<nowiki/>'''''ॉमिनेट करता है''', तो: ''g''(''s''<sub>1</sub>) ≤ ''r<sup>G</sup>'' · ''g''(''s<sub>2</sub>'') (न्यूनतमीकरण समस्याओं में); ''g''(''s''<sub>1</sub>) ≥ ''r<sup>(-G)</sup>'' · ''g''(''s<sub>2</sub>'') (अधिकतमीकरण समस्याओं में)।
#* यदि एस<sub>1</sub> एस पर हावी है<sub>2</sub>, फिर जी(एस<sub>1</sub>) ≤ जी(एस<sub>2</sub>) (समस्याओं को न्यूनतम करने में); जी(एस<sub>1</sub>) ≥ जी(एस<sub>2</sub>) (अधिकतमीकरण समस्याओं में)।
#* यदि ''s''<sub>1</sub> ''s''<sub>2</sub> को डॉमिनेट करता है, तो: g(''s''<sub>1</sub>) ≤ g(''s''<sub>2</sub>) (न्यूनतमीकरण समस्याओं में); g(''s''<sub>1</sub>) ≥ g(''s''<sub>2</sub>) (अधिकतमीकरण समस्याओं में)।
# तकनीकी शर्तें (उपरोक्त के अतिरिक्त):
# ''तकनीकी शर्तें'' (उपरोक्त के अतिरिक्त):
#* अर्ध-प्रभुत्व संबंध को बहुपद समय में तय किया जा सकता है।
#* क्वासी-डॉमिनेटता संबंध को बिनोमिक समय में तय किया जा सकता है।
# फ़िल्टर फ़ंक्शंस पर शर्तें: किसी भी r>1 के लिए, किसी भी फ़िल्टर फ़ंक्शन h के लिए H में, किसी भी इनपुट-वेक्टर x के लिए, और किन्हीं दो स्टेट-वेक्टर s के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है:
# ''फ़िल्टर फलनों पर शर्तें'': किसी भी ''r''>1 के लिए, किसी भी फ़िल्टर फलन ''h, H'' में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिश ''s''<sub>1</sub>,''s''<sub>2</sub> के लिए, निम्नलिखित सत्य है:
#* यदि ''s''<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>,'' और एस<sub>1</sub> अर्ध-प्रभुत्व एस<sub>2</sub>'', फिर ''एच''(''एस''<sub>1</sub>,x) ≥ h(s<sub>2</sub>,एक्स)'।
#* यदि '''s<sub>1</sub> s<sub>2</sub> के प्रति (d,r)-संवृत है, और s<sub>1</sub> s<sub>2</sub> को क्वासी-डॉमिनेट करता है''', तो '''''h(s<sub>1</sub>,x) ≥ h(s<sub>2</sub>,x)'''''।
#* यदि एस<sub>1</sub> एस पर हावी है<sub>2</sub>, फिर h(s<sub>1</sub>,x) ≥ h(s<sub>2</sub>,एक्स)।
#* यदि ''s''<sub>1</sub> ''s''<sub>2</sub> को डॉमिनेट करता है, तो h(''s<sub>1</sub>'',x) ≥ h(''s''<sub>2</sub>,x)।


प्रत्येक परोपकारी समस्या के लिए, गतिशील प्रोग्राम को दो बदलावों (बोल्डफेस्ड) के साथ उपरोक्त के समान एफपीटीएएस में परिवर्तित किया जा सकता है:
प्रत्येक बेनिवॉलेंट समस्या के लिए, डायनेमिक प्रोग्राम को उसी तरीके से एक एफपीटीएएस में बदला जा सकता है जैसा कि ऊपर वाले में किया गया है, दो परिवर्तनों (निर्भीक) के साथ:
* चलो टी<sub>0</sub> := एस<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय.
* मान लीजिए ''T''<sub>0</sub> := ''S''<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय।
* k = 1 से n के लिए करें:
* k = 1 से n के लिए करें:
** चलो यू<sub>k</sub> := {एफ<sub>j</sub>(एस,एक्स<sub>k</sub>) | एफ<sub>j</sub>एफ में, टी में एस<sub>k</sub><sub>−1</sub>, ''एच<sub>j</sub>(एस,एक्स<sub>k</sub>)=सत्य' }, जहां h<sub>j</sub>संक्रमण फ़ंक्शन f के अनुरूप फ़िल्टर फ़ंक्शन है<sub>j</sub>.
** मान लीजिए ''U''<sub>k</sub> := {''f<sub>j</sub>''(''s'',''x<sub>k</sub>'') | ''f<sub>j</sub>'' in ''F'', ''s'' in ''T<sub>k</sub>''<sub>−1</sub>, '''''h<sub>j</sub>''(''s'',''x<sub>k</sub>'')=True''' }, जहां ''h''<sub>j</sub> संक्रमण फलन ''f<sub>j</sub>'' के अनुरूप फ़िल्टर फलन है।
**मान लीजिए टी<sub>k</sub>:= यू की एक छंटनी प्रति<sub>k</sub>: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं<sub>k</sub>, एक ऐसा तत्व चुनें जो यू में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता हो<sub>k</sub>,' और इसे टी में डालें<sub>k</sub>.
**मान लीजिए ''T<sub>k</sub>'' := ''U''<sub>k</sub> की एक छंटनी की गई प्रति: प्रत्येक ''r''-बॉक्स के लिए जिसमें ''U''<sub>k</sub> के एक या अधिक स्थिति सम्मिलित हैं, एक एकल तत्व चुनें जो '''''U''<sub>k</sub> में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता है''', और इसे ''T''<sub>k</sub> में डालें।
* आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस<sub>n</sub>}.
* आउटपुट का न्यूनतम/अधिकतम {g(s) | s in ''T<sub>n</sub>''}


==== उदाहरण ====
==== उदाहरण ====
यहां परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।<ref name=":0" />
यहां बेनिवॉलेंट समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।<ref name=":0" />


1. 0-1 [[बस्ता समस्या]] कल्याणकारी है। यहां, हमारे पास a=2 है: प्रत्येक इनपुट 2-वेक्टर (वजन, मान) है। बी=2 के साथ एक डीपी है: प्रत्येक राज्य एनकोड करता है (वर्तमान वजन, वर्तमान मूल्य)दो संक्रमण कार्य हैं: एफ<sub>1</sub> अगला इनपुट आइटम जोड़ने से मेल खाता है, और एफ<sub>2</sub> इसे न जोड़ने से मेल खाता है। संबंधित फ़िल्टर फ़ंक्शन हैं: h<sub>1</sub> सत्यापित करता है कि अगले इनपुट आइटम का वजन अधिकतम नैपसेक क्षमता पर है; एच<sub>2</sub> हमेशा सत्य लौटाता है। मान फ़ंक्शन g(s) s लौटाता है<sub>2</sub>. प्रारंभिक अवस्था-सेट {(0,0)} है। डिग्री वेक्टर (1,1) है। प्रभुत्व का रिश्ता तुच्छ है. अर्ध-प्रभुत्व संबंध केवल भार निर्देशांक की तुलना करता है: s अर्ध-प्रभुत्व t यदि s<sub>1</sub> ≤ टी<sub>1</sub>. इसका निहितार्थ यह है कि, यदि राज्य t का भार राज्य s से अधिक है, तो संक्रमण कार्यों को t और s के बीच निकटता को संरक्षित नहीं करने की अनुमति है (उदाहरण के लिए, यह संभव है कि s का कोई उत्तराधिकारी हो और t के पास कोई संगत उत्तराधिकारी न हो)। इसी तरह का एल्गोरिदम पहले इबारा और किम द्वारा प्रस्तुत किया गया था।<ref>{{Cite journal|last1=Ibarra|first1=Oscar H.|last2=Kim|first2=Chul E.|date=1975-10-01|title=नैपसैक और सबसेट समस्याओं के योग के लिए तेज़ सन्निकटन एल्गोरिदम|url=https://doi.org/10.1145/321906.321909|journal=Journal of the ACM|volume=22|issue=4|pages=463–468|doi=10.1145/321906.321909|s2cid=14619586|issn=0004-5411}}</ref> इस FPTAS के रन-टाइम को बेहतर बनाया जा सकता है <math>O(n \log{1/\epsilon} + 1/\epsilon^4)</math> पूर्णांकों पर संचालन.<ref>{{Cite journal|last=Lawler|first=Eugene L.|date=1979-11-01|title=नैपसेक समस्याओं के लिए तेज़ सन्निकटन एल्गोरिदम|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.4.4.339|journal=Mathematics of Operations Research|volume=4|issue=4|pages=339–356|doi=10.1287/moor.4.4.339|s2cid=7655435|issn=0364-765X}}</ref> बाद में घातांक को सुधार कर 2.5 कर दिया गया।<ref>{{Cite thesis|title=नैपसैक समस्याओं के लिए तेज़ पूर्णतः बहुपद सन्निकटन योजनाएँ|url=https://dspace.mit.edu/handle/1721.1/98564|publisher=Massachusetts Institute of Technology|date=2015|degree=Thesis|first=Donguk|last=Rhee|hdl=1721.1/98564}}</ref>
1. 0-1 [[बस्ता समस्या|नैपसैक समस्या]] बेनिवॉलेंट है। यहाँ, ''a''=2 है: प्रत्येक इनपुट एक 2-सदिश (वेट, मूल्य) होता है। हमारे पास ''b''=2 है: प्रत्येक स्थिति (वर्तमान वेट, वर्तमान मूल्य) को कोड करती है। दो परियोजना फलन होते हैं: ''f<sub>1</sub>'' अगले इनपुट आइटम को जोड़ने का संदर्भ देता है, और ''f<sub>2</sub>'' उसे नहीं जोड़ने का। उसके संबंधित फ़िल्टर फलन हैं: ''h<sub>1</sub>'' यह सत्यापित करता है कि अगले इनपुट आइटम का वेट किन्नर क्षमता से कम है; h2 हमेशा सच की वापसी करता है। मूल्य फलन ''g''(''s'') ''s''<sub>2</sub> को वापसी करता है। प्रारंभिक स्थिति-समुच्चय है ''{(0,0)}''। डिग्री सदिश ''(1,1)'' है। डॉमिनेट संबंध घटित है। क्वासी-डॉमिनेटता संबंध केवल वेट समन्वय करता है: ''s'' ने तीव्रीक संबंध है तब ''t'' का वेट ''t<sub>1</sub>'' से कम या बराबर होता है। इसका अर्थ है कि, यदि स्थिति ''t'' का स्थिति ''s'' से अधिक वेट है, तो परियोजना फलनों को तकनीकी रूप से ''t'' और ''s'' के बीच समर्पण को संरक्षित नहीं करने की अनुमति है (यह संभव है, उदाहरणार्थ, कि ''s'' के एक सफलता कारक है और ''t'' का उसके समर्पक का उपयुक्त सफलता कारक नहीं है)। एक समान एल्गोरिथ्म पहले Ibarra और Kim ने प्रस्तुत किया था।<ref>{{Cite journal|last1=Ibarra|first1=Oscar H.|last2=Kim|first2=Chul E.|date=1975-10-01|title=नैपसैक और सबसेट समस्याओं के योग के लिए तेज़ सन्निकटन एल्गोरिदम|url=https://doi.org/10.1145/321906.321909|journal=Journal of the ACM|volume=22|issue=4|pages=463–468|doi=10.1145/321906.321909|s2cid=14619586|issn=0004-5411}}</ref> इस एफपीटीएएस की रनटाइम को <math>O(n \log{1/\epsilon} + 1/\epsilon^4)</math> पूर्णांकों पर क्रियाएँ करने के लिए सुधारा जा सकता है।<ref>{{Cite journal|last=Lawler|first=Eugene L.|date=1979-11-01|title=नैपसेक समस्याओं के लिए तेज़ सन्निकटन एल्गोरिदम|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.4.4.339|journal=Mathematics of Operations Research|volume=4|issue=4|pages=339–356|doi=10.1287/moor.4.4.339|s2cid=7655435|issn=0364-765X}}</ref> गुणक पश्चात्तल में 2.5 तक सुधारा गया था।<ref>{{Cite thesis|title=नैपसैक समस्याओं के लिए तेज़ पूर्णतः बहुपद सन्निकटन योजनाएँ|url=https://dspace.mit.edu/handle/1721.1/98564|publisher=Massachusetts Institute of Technology|date=2015|degree=Thesis|first=Donguk|last=Rhee|hdl=1721.1/98564}}</ref>
* नोट: 2-भारित नैपसेक समस्या पर विचार करें, जहां प्रत्येक वस्तु के दो वजन और एक मूल्य होता है, और लक्ष्य मूल्य को अधिकतम करना है ताकि कुल वजन के वर्गों का योग अधिकतम नैपसेक क्षमता हो: <math>\left(\sum_{k\in K} w_{1,k}\right)^2 + \left(\sum_{k\in K} w_{2,k}\right)^2 \leq W</math>. हम इसे एक समान डीपी का उपयोग करके हल कर सकते हैं, जहां प्रत्येक स्थिति (वर्तमान वजन 1, वर्तमान वजन 2, मूल्य) है। अर्ध-प्रभुत्व संबंध को इस प्रकार संशोधित किया जाना चाहिए: s अर्ध-प्रभुत्व t iff (s)।<sub>1</sub><sup>2</sup>+s<sub>2</sub><sup>2</sup>) ≤ (t<sub>1</sub><sup>2</sup>+t<sub>2</sub><sup>2</sup>). लेकिन यह उपरोक्त शर्त 1 का उल्लंघन करता है: अर्ध-प्रभुत्व संक्रमण कार्यों द्वारा संरक्षित नहीं है [उदाहरण के लिए, राज्य (2,2,..) अर्ध-प्रभुत्व (1,3,..); लेकिन दोनों राज्यों में इनपुट (2,0,..) जोड़ने के बाद, परिणाम (4,2,..) अर्ध-प्रभुत्व (3,3,..)] नहीं होता है। अतः प्रमेय का प्रयोग नहीं किया जा सकता। वास्तव में, इस समस्या का कोई FPTAS नहीं है जब तक कि P=NP हो। द्वि-आयामी नैपसेक समस्या के लिए भी यही सच है। [[एकाधिक उपसमुच्चय योग]] समस्या के लिए भी यही सच है: अर्ध-प्रभुत्व संबंध होना चाहिए: s अर्ध-प्रभुत्व t यदि अधिकतम<sub>1,</sub>s<sub>2</sub>) ≤ अधिकतम(t<sub>1,</sub>t<sub>2</sub>), लेकिन यह उपरोक्त उदाहरण के अनुसार, परिवर्तनों द्वारा संरक्षित नहीं है।
* नोट: 2-वेटेड नैपसैक समस्या में, जहाँ प्रत्येक आइटम के दो वेट और एक मूल्य होता है, और लक्ष्य होता है कि विल्यू बढ़ाएं ताकि कुल वेट के वर्गों का योग किन्नर क्षमता से कम या बराबर हो: <math>\left(\sum_{k\in K} w_{1,k}\right)^2 + \left(\sum_{k\in K} w_{2,k}\right)^2 \leq W</math>हम इसे एक समान डीपी का उपयोग करके हल कर सकते हैं, जहाँ प्रत्येक स्थिति (वर्तमान वेट 1, वर्तमान वेट 2, मूल्य) होती है। क्वासी-डॉमिनेटता संबंध को बदलकर किया जाना चाहिए: ''s'' तीव्रीक तो ''t'' iff (''s''<sub>1</sub><sup>2</sup> + ''s''<sub>2</sub><sup>2</sup>) ≤ (''t''<sub>1</sub><sup>2</sup> + ''t''<sub>2</sub><sup>2</sup>)लेकिन यह शर्त 1 का उल्लंघन करता है: क्वासी-डॉमिनेटता संबंध संक्रिया फलन द्वारा संरक्षित नहीं किया जाता है, उदाहरण के लिए, स्थिति (2,2,..) (1,3,..) को क्वासी-डॉमिनेटता करती है; लेकिन उसके बाद जब इनपुट (2,0,..) को दोनों स्थितियों में जोड़ते हैं, परिणाम (4,2,..) (3,3,..) को क्वासी-डॉमिनेटता नहीं करता है। इसलिए यह सिद्धांत का उपयोग नहीं किया जा सकता है। वास्तव में, यह समस्या एफपीटीएएस नहीं है जब तक P=NP नहीं हो। ऐसा ही दो-विमीय नैपसैक समस्या के लिए भी है। ऐसा ही [[एकाधिक उपसमुच्चय योग|एकाधिक उपसमुच्चय समस्या]] के लिए भी है: क्वासी-डॉमिनेटता संबंध इस तरह होना चाहिए: ''s'' तीव्रीक तो ''t'' iff max(''s''<sub>1,</sub>''s''<sub>2</sub>) ≤ max(''t''<sub>1,</sub>''t''<sub>2</sub>), लेकिन यह संक्रियाओं द्वारा संरक्षित नहीं किया जाता है, उपर दिए गए उदाहरण की तरह।


2. एक ही मशीन पर विलंबित कार्यों की भारित संख्या को कम करना, या प्रारंभिक कार्यों की भारित संख्या को अधिकतम करना; निरूपित 1||<math>\sum w_j U_j</math>.
2. एकल मशीन पर टार्डी जॉब्स की वेटेड संख्या को कम करने के लिए, या अलगाव जॉब्स की वेटेड संख्या को बढ़ाने के लिए; चिह्नित 1||<math>\sum w_j U_j</math>


3. विलंबित कार्यों की भारित संख्या को कम करने के लिए बैच शेड्यूलिंग: 1|बैच|<math>\sum w_j U_j</math>.
3. वफसवान जॉब्स की वेटेड संख्या को कम करने के लिए बैच अनुसूचना: 1|बैच|<math>\sum w_j U_j</math>


4. एक ही मशीन पर नौकरियों के बिगड़ने का कारण: 1|बिगड़ना|<math>\max C_j</math>.
4. एकल मशीन पर डेटेरियरेटिंग जॉब्स की मेक्सपैन: 1|डिटीरियोरेट|<math>\max C_j</math>


5. एक मशीन पर कुल देर से काम: 1||<math>\sum V_j</math>.
5. एकल मशीन पर कार्य में विलंब: 1||<math>\sum V_j</math>


6. एक मशीन पर कुल भारित विलंबित कार्य: 1||<math>\sum w_j V_j</math>.
6. एकल मशीन पर कुल वेटेड कार्य में विलंब: 1||<math>\sum w_j V_j</math>


=== गैर-उदाहरण ===
=== गैर-उदाहरण ===
उपरोक्त परिणाम की व्यापकता के बावजूद, ऐसे मामले हैं जिनमें इसका उपयोग नहीं किया जा सकता है।
उपरोक्त परिणाम की व्यापकता के बावजूद, ऐसे ऐसी स्थिति हैं जहां इसका उपयोग नहीं किया जा सकता है।
 
1. कुल विलंबता समस्या में 1||<math>\sum T_j</math>, लॉलर का गतिशील प्रोग्रामिंग सूत्रीकरण<ref>{{Citation|last=Lawler|first=Eugene L.|title=A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X|date=1977-01-01|url=https://www.sciencedirect.com/science/article/pii/S0167506008707428|work=Annals of Discrete Mathematics|volume=1|pages=331–342|editor-last=Hammer|editor-first=P. L.|series=Studies in Integer Programming|publisher=Elsevier|doi=10.1016/S0167-5060(08)70742-8|language=en|access-date=2021-12-17|editor2-last=Johnson|editor2-first=E. L.|editor3-last=Korte|editor3-first=B. H.|editor4-last=Nemhauser|editor4-first=G. L.}}</ref> पुराने राज्य स्थान के सभी राज्यों को कुछ B बार अद्यतन करने की आवश्यकता है, जहाँ B, X (अधिकतम इनपुट आकार) के क्रम का है। आर्थिक लॉट-साइज़िंग के लिए डीपी के लिए भी यही सच है।<ref>{{Cite journal|last1=Florian|first1=M.|last2=Lenstra|first2=J. K.|last3=Rinnooy Kan|first3=A. H. G.|date=1980-07-01|title=Deterministic Production Planning: Algorithms and Complexity|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.26.7.669|journal=Management Science|volume=26|issue=7|pages=669–679|doi=10.1287/mnsc.26.7.669|issn=0025-1909}}</ref> इन मामलों में, एफ में संक्रमण कार्यों की संख्या बी है, जो लॉग (एक्स) में घातीय है, इसलिए दूसरी तकनीकी स्थिति का उल्लंघन होता है। स्टेट-ट्रिमिंग तकनीक उपयोगी नहीं है, लेकिन एक अन्य तकनीक - इनपुट-राउंडिंग - का उपयोग एफपीटीएएस को डिजाइन करने के लिए किया गया है।<ref>{{Cite journal|last=Lawler|first=E. L.|date=1982-12-01|title=संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना|url=https://dx.doi.org/10.1016/0167-6377%2882%2990022-0|journal=Operations Research Letters|language=en|volume=1|issue=6|pages=207–208|doi=10.1016/0167-6377(82)90022-0|issn=0167-6377}}</ref><ref>{{Cite journal|last1=van Hoesel|first1=C. P. M.|last2=Wagelmans|first2=Albert|date=1997-01-01|title=एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं|url=https://repub.eur.nl/pub/1406/|language=en}}</ref>
2. विचरण न्यूनीकरण समस्या 1|| में<math>CTV</math>, वस्तुनिष्ठ कार्य है  <math>g(s) = s_5 - (s_4-s_3)^2/n</math>, जो शर्त 2 का उल्लंघन करता है, इसलिए प्रमेय का उपयोग नहीं किया जा सकता है। लेकिन एफपीटीएएस को डिजाइन करने के लिए विभिन्न तकनीकों का उपयोग किया गया है।<ref>{{Cite journal|last=Cai|first=X.|date=1995-09-21|title=एकल मशीन प्रणालियों में सहमत रूप से भारित विचरण को न्यूनतम करना|url=https://dx.doi.org/10.1016/0377-2217%2893%29E0367-7|journal=European Journal of Operational Research|language=en|volume=85|issue=3|pages=576–592|doi=10.1016/0377-2217(93)E0367-7|issn=0377-2217}}</ref><ref>{{Cite journal|last=Woeginger|first=Gerhard J.|date=1999-05-01|title=एक ही मशीन पर सहमत रूप से भारित भिन्नता को न्यूनतम करने के लिए एक अनुमान योजना|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.11.2.211|journal=INFORMS Journal on Computing|volume=11|issue=2|pages=211–216|doi=10.1287/ijoc.11.2.211|issn=1091-9856}}</ref>


1. कुल टार्डिनेस समस्या 1||<math>\sum T_j</math> में, लॉलर<ref>{{Citation|last=Lawler|first=Eugene L.|title=A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X|date=1977-01-01|url=https://www.sciencedirect.com/science/article/pii/S0167506008707428|work=Annals of Discrete Mathematics|volume=1|pages=331–342|editor-last=Hammer|editor-first=P. L.|series=Studies in Integer Programming|publisher=Elsevier|doi=10.1016/S0167-5060(08)70742-8|language=en|access-date=2021-12-17|editor2-last=Johnson|editor2-first=E. L.|editor3-last=Korte|editor3-first=B. H.|editor4-last=Nemhauser|editor4-first=G. L.}}</ref> के डायनेमिक प्रोग्रामिंग सूत्र को अपडेट करने की आवश्यकता होती है, जिसमें पुराने स्थिति स्थान के सभी स्थितियों को कुछ ''B'' बार अपडेट किया जाता है, जहाँ ''B, X'' (अधिकतम इनपुट आकार) के आदर्श में होता है। यही समान ब्यवहार आर्थिक लॉट-साइजिंग के लिए डीपी के लिए भी होता है।<ref>{{Cite journal|last1=Florian|first1=M.|last2=Lenstra|first2=J. K.|last3=Rinnooy Kan|first3=A. H. G.|date=1980-07-01|title=Deterministic Production Planning: Algorithms and Complexity|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.26.7.669|journal=Management Science|volume=26|issue=7|pages=669–679|doi=10.1287/mnsc.26.7.669|issn=0025-1909}}</ref> इन स्थितियों में, ''F'' में परियोजना फलनों की संख्या ''B'' होती है, जो लॉग(X) में अपेक्षित होती है, इसलिए दूसरी तकनीकी शर्त का उल्लंघन हो जाता है। स्थिति-काटन तकनीक उपयोगी नहीं होती है, लेकिन एक दूसरी तकनीक - इनपुट-राउंडिंग - का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।<ref>{{Cite journal|last=Lawler|first=E. L.|date=1982-12-01|title=संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना|url=https://dx.doi.org/10.1016/0167-6377%2882%2990022-0|journal=Operations Research Letters|language=en|volume=1|issue=6|pages=207–208|doi=10.1016/0167-6377(82)90022-0|issn=0167-6377}}</ref><ref>{{Cite journal|last1=van Hoesel|first1=C. P. M.|last2=Wagelmans|first2=Albert|date=1997-01-01|title=एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं|url=https://repub.eur.nl/pub/1406/|language=en}}</ref>


== कुछ अन्य समस्याएं जिनमें एफपीटीएएस == है
2. वैरिएंस मिनिमाइजेशन समस्या 1||<math>CTV</math> में, उद्देश्य फलन <math>g(s) = s_5 - (s_4-s_3)^2/n</math> है, जो शर्त 2 का उल्लंघन करता है, इसलिए सिद्धांत का उपयोग नहीं किया जा सकता है। लेकिन विभिन्न तकनीकों का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।<ref>{{Cite journal|last=Cai|first=X.|date=1995-09-21|title=एकल मशीन प्रणालियों में सहमत रूप से भारित विचरण को न्यूनतम करना|url=https://dx.doi.org/10.1016/0377-2217%2893%29E0367-7|journal=European Journal of Operational Research|language=en|volume=85|issue=3|pages=576–592|doi=10.1016/0377-2217(93)E0367-7|issn=0377-2217}}</ref><ref>{{Cite journal|last=Woeginger|first=Gerhard J.|date=1999-05-01|title=एक ही मशीन पर सहमत रूप से भारित भिन्नता को न्यूनतम करने के लिए एक अनुमान योजना|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.11.2.211|journal=INFORMS Journal on Computing|volume=11|issue=2|pages=211–216|doi=10.1287/ijoc.11.2.211|issn=1091-9856}}</ref>


== कुछ अन्य समस्याएं जिनमें एफपीटीएएस है ==
*नैपसेक समस्या,<ref>{{Cite book|last=Vazirani|first=Vijay|url=https://archive.org/details/approximationalg00vazi_328|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2001|isbn=3540653678|location=Berlin|pages=[https://archive.org/details/approximationalg00vazi_328/page/n69 69]–70|oclc=47097680|url-access=limited}}</ref><ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|date=2004-03-01|title=नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग|url=https://doi.org/10.1023/B:JOCO.0000021934.29833.6b|journal=Journal of Combinatorial Optimization|language=en|volume=8|issue=1|pages=5–11|doi=10.1023/B:JOCO.0000021934.29833.6b|s2cid=36474745|issn=1573-2886}}</ref> साथ ही इसके कुछ प्रकार:
*नैपसेक समस्या,<ref>{{Cite book|last=Vazirani|first=Vijay|url=https://archive.org/details/approximationalg00vazi_328|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2001|isbn=3540653678|location=Berlin|pages=[https://archive.org/details/approximationalg00vazi_328/page/n69 69]–70|oclc=47097680|url-access=limited}}</ref><ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|date=2004-03-01|title=नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग|url=https://doi.org/10.1023/B:JOCO.0000021934.29833.6b|journal=Journal of Combinatorial Optimization|language=en|volume=8|issue=1|pages=5–11|doi=10.1023/B:JOCO.0000021934.29833.6b|s2cid=36474745|issn=1573-2886}}</ref> साथ ही इसके कुछ प्रकार:
**0-1 बस्ता समस्या।<ref>{{cite book|last=Jin|first=Ce|title=0-1 नैपसेक के लिए एक बेहतर एफपीटीएएस|series=Leibniz International Proceedings in Informatics (LIPIcs)|year=2019|volume=132|pages=76:1–76:14|doi=10.4230/LIPIcs.ICALP.2019.76 | arxiv=1904.09562|isbn=9783959771092|s2cid=128317990}}</ref>
**0-1 नैपसेक समस्या।<ref>{{cite book|last=Jin|first=Ce|title=0-1 नैपसेक के लिए एक बेहतर एफपीटीएएस|series=Leibniz International Proceedings in Informatics (LIPIcs)|year=2019|volume=132|pages=76:1–76:14|doi=10.4230/LIPIcs.ICALP.2019.76 | arxiv=1904.09562|isbn=9783959771092|s2cid=128317990}}</ref>
**अनबाउंडेड नैपसेक समस्या।<ref>{{Cite journal|last1=Jansen|first1=Klaus|last2=Kraft|first2=Stefan E. J.|date=2018-02-01|title=अनबाउंडेड नैपसैक समस्या के लिए एक तेज़ एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0195669817301245|journal=European Journal of Combinatorics|series=Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller|language=en|volume=68|pages=148–174|doi=10.1016/j.ejc.2017.07.016|arxiv=1504.04650|s2cid=9557898|issn=0195-6698}}</ref>
**अनपरिबद्ध नैपसैक समस्या।<ref>{{Cite journal|last1=Jansen|first1=Klaus|last2=Kraft|first2=Stefan E. J.|date=2018-02-01|title=अनबाउंडेड नैपसैक समस्या के लिए एक तेज़ एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0195669817301245|journal=European Journal of Combinatorics|series=Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller|language=en|volume=68|pages=148–174|doi=10.1016/j.ejc.2017.07.016|arxiv=1504.04650|s2cid=9557898|issn=0195-6698}}</ref>
**डेल्टा-मॉड्यूलर बाधाओं के साथ बहुआयामी नैपसेक समस्या।<ref>{{cite book|last=Gribanov|first=D. V.|date=2021-05-10|title=गणितीय अनुकूलन सिद्धांत और संचालन अनुसंधान|chapter=An FPTAS for the $$\var ''Delta'' $$-Modular Multidimensional Knapsack Problem |series=Lecture Notes in Computer Science |volume=12755 |pages=79–95 |doi=10.1007/978-3-030-77876-7_6 |arxiv=2103.07257|isbn=978-3-030-77875-0 |s2cid=232222954 }}</ref>
**डेल्टा-मॉड्यूलर बाधाओं के साथ बहुविमीय नैपसेक समस्या।<ref>{{cite book|last=Gribanov|first=D. V.|date=2021-05-10|title=गणितीय अनुकूलन सिद्धांत और संचालन अनुसंधान|chapter=An FPTAS for the $$\var ''Delta'' $$-Modular Multidimensional Knapsack Problem |series=Lecture Notes in Computer Science |volume=12755 |pages=79–95 |doi=10.1007/978-3-030-77876-7_6 |arxiv=2103.07257|isbn=978-3-030-77875-0 |s2cid=232222954 }}</ref>
**बहुउद्देश्यीय 0-1 बस्ता समस्या।<ref>{{Cite journal|last1=Bazgan|first1=Cristina|last2=Hugot|first2=Hadrien|last3=Vanderpooten|first3=Daniel|date=2009-10-01|title=Implementing an efficient fptas for the 0–1 multi-objective knapsack problem|url=https://www.sciencedirect.com/science/article/pii/S0377221708006905|journal=European Journal of Operational Research|language=en|volume=198|issue=1|pages=47–56|doi=10.1016/j.ejor.2008.07.047|issn=0377-2217}}</ref>
**बहुउद्देश्यीय 0-1 नैपसेक समस्या।<ref>{{Cite journal|last1=Bazgan|first1=Cristina|last2=Hugot|first2=Hadrien|last3=Vanderpooten|first3=Daniel|date=2009-10-01|title=Implementing an efficient fptas for the 0–1 multi-objective knapsack problem|url=https://www.sciencedirect.com/science/article/pii/S0377221708006905|journal=European Journal of Operational Research|language=en|volume=198|issue=1|pages=47–56|doi=10.1016/j.ejor.2008.07.047|issn=0377-2217}}</ref>
**पैरामीट्रिक नैपसेक समस्या।<ref>{{Cite journal|last1=Holzhauser|first1=Michael|last2=Krumke|first2=Sven O.|date=2017-10-01|title=पैरामीट्रिक नैपसेक समस्या के लिए एक एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0020019017301072|journal=Information Processing Letters|language=en|volume=126|pages=43–47|doi=10.1016/j.ipl.2017.06.006|arxiv=1701.07822|s2cid=1013794|issn=0020-0190}}</ref>
**पैरामीट्रिक नैपसेक समस्या।<ref>{{Cite journal|last1=Holzhauser|first1=Michael|last2=Krumke|first2=Sven O.|date=2017-10-01|title=पैरामीट्रिक नैपसेक समस्या के लिए एक एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0020019017301072|journal=Information Processing Letters|language=en|volume=126|pages=43–47|doi=10.1016/j.ipl.2017.06.006|arxiv=1701.07822|s2cid=1013794|issn=0020-0190}}</ref>
**सममित द्विघात बस्ता समस्या।<ref>{{Cite journal|last=Xu|first=Zhou|date=2012-04-16|title=सममित द्विघात नैपसैक समस्या के लिए एक प्रबल बहुपद FPTAS|url=https://www.sciencedirect.com/science/article/pii/S0377221711010022|journal=European Journal of Operational Research|language=en|volume=218|issue=2|pages=377–381|doi=10.1016/j.ejor.2011.10.049|issn=0377-2217}}</ref>
**सममित द्विघात नैपसेक समस्या।<ref>{{Cite journal|last=Xu|first=Zhou|date=2012-04-16|title=सममित द्विघात नैपसैक समस्या के लिए एक प्रबल बहुपद FPTAS|url=https://www.sciencedirect.com/science/article/pii/S0377221711010022|journal=European Journal of Operational Research|language=en|volume=218|issue=2|pages=377–381|doi=10.1016/j.ejor.2011.10.049|issn=0377-2217}}</ref>
* गणना-उपसमुच्चय-योग (#सबसेट योग समस्या) - अधिकतम सी के योग के साथ अलग-अलग उपसमुच्चय की संख्या ज्ञात करना।<ref>{{Cite book|last1=Gopalan|first1=Parikshit|last2=Klivans|first2=Adam|last3=Meka|first3=Raghu|last4=Štefankovic|first4=Daniel|last5=Vempala|first5=Santosh|last6=Vigoda|first6=Eric|title=2011 IEEE 52nd Annual Symposium on Foundations of Computer Science |chapter=An FPTAS for #Knapsack and Related Counting Problems |date=2011-10-01|chapter-url=https://ieeexplore.ieee.org/abstract/document/6108252?|pages=817–826|doi=10.1109/FOCS.2011.32|isbn=978-0-7695-4571-4|s2cid=5691574}}</ref>
* गणना-उपसमुच्चय-योग (#उपसमुच्चय योग समस्या) - अधिकतम सी के योग के साथ अलग-अलग उपसमुच्चय की संख्या ज्ञात करना।<ref>{{Cite book|last1=Gopalan|first1=Parikshit|last2=Klivans|first2=Adam|last3=Meka|first3=Raghu|last4=Štefankovic|first4=Daniel|last5=Vempala|first5=Santosh|last6=Vigoda|first6=Eric|title=2011 IEEE 52nd Annual Symposium on Foundations of Computer Science |chapter=An FPTAS for #Knapsack and Related Counting Problems |date=2011-10-01|chapter-url=https://ieeexplore.ieee.org/abstract/document/6108252?|pages=817–826|doi=10.1109/FOCS.2011.32|isbn=978-0-7695-4571-4|s2cid=5691574}}</ref>
*प्रतिबंधित सबसे छोटा पथ समस्या: विलंब बाधा के अधीन, ग्राफ़ में दो नोड्स के बीच न्यूनतम लागत वाला पथ ढूंढना।<ref>{{Cite journal|last1=Ergun|first1=Funda|last2=Sinha|first2=Rakesh|last3=Zhang|first3=Lisa|date=2002-09-15|title=प्रतिबंधित सबसे छोटे पथ के लिए एक बेहतर एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0020019002002053|journal=Information Processing Letters|language=en|volume=83|issue=5|pages=287–291|doi=10.1016/S0020-0190(02)00205-3|issn=0020-0190}}</ref>
*प्रतिबंधित सबसे छोटा पथ समस्या: विलंब बाधा के अधीन, ग्राफ़ में दो नोड्स के बीच न्यूनतम लागत वाला पथ ढूंढना।<ref>{{Cite journal|last1=Ergun|first1=Funda|last2=Sinha|first2=Rakesh|last3=Zhang|first3=Lisa|date=2002-09-15|title=प्रतिबंधित सबसे छोटे पथ के लिए एक बेहतर एफपीटीएएस|url=https://www.sciencedirect.com/science/article/pii/S0020019002002053|journal=Information Processing Letters|language=en|volume=83|issue=5|pages=287–291|doi=10.1016/S0020-0190(02)00205-3|issn=0020-0190}}</ref>
*सबसे छोटे रास्ते और गैर-रैखिक उद्देश्य।<ref>{{Cite journal|last1=Tsaggouris|first1=George|last2=Zaroliagis|first2=Christos|date=2009-06-01|title=Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications|url=https://doi.org/10.1007/s00224-007-9096-4|journal=Theory of Computing Systems|language=en|volume=45|issue=1|pages=162–186|doi=10.1007/s00224-007-9096-4|s2cid=13010023|issn=1433-0490}}</ref>
*सबसे छोटे रास्ते और गैर-रैखिक उद्देश्य।<ref>{{Cite journal|last1=Tsaggouris|first1=George|last2=Zaroliagis|first2=Christos|date=2009-06-01|title=Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications|url=https://doi.org/10.1007/s00224-007-9096-4|journal=Theory of Computing Systems|language=en|volume=45|issue=1|pages=162–186|doi=10.1007/s00224-007-9096-4|s2cid=13010023|issn=1433-0490}}</ref>
*[[ किनारे का आवरण ]] की गिनती|एज-कवर।<ref>{{Citation|last1=Lin|first1=Chengyu|title=A Simple FPTAS for Counting Edge Covers|date=2013-12-18|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.25|work=Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)|pages=341–348|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611973402.25|isbn=978-1-61197-338-9|access-date=2021-12-13|last2=Liu|first2=Jingcheng|last3=Lu|first3=Pinyan|arxiv=1309.6115|s2cid=14598468}}</ref>
*[[ किनारे का आवरण |एज-कवर]] की गणना<ref>{{Citation|last1=Lin|first1=Chengyu|title=A Simple FPTAS for Counting Edge Covers|date=2013-12-18|url=https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.25|work=Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)|pages=341–348|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611973402.25|isbn=978-1-61197-338-9|access-date=2021-12-13|last2=Liu|first2=Jingcheng|last3=Lu|first3=Pinyan|arxiv=1309.6115|s2cid=14598468}}</ref>
*वेक्टर उपसमुच्चय खोज समस्या जहां आयाम निश्चित है।<ref>{{Cite journal|last1=Kel’manov|first1=A. V.|last2=Romanchenko|first2=S. M.|date=2014-07-01|title=वेक्टर उपसमुच्चय खोज समस्या के लिए एक FPTAS|url=https://doi.org/10.1134/S1990478914030041|journal=Journal of Applied and Industrial Mathematics|language=en|volume=8|issue=3|pages=329–336|doi=10.1134/S1990478914030041|s2cid=96437935|issn=1990-4797}}</ref>
*सदिश उपसमुच्चय खोज समस्या जहां विमा निश्चित है।<ref>{{Cite journal|last1=Kel’manov|first1=A. V.|last2=Romanchenko|first2=S. M.|date=2014-07-01|title=वेक्टर उपसमुच्चय खोज समस्या के लिए एक FPTAS|url=https://doi.org/10.1134/S1990478914030041|journal=Journal of Applied and Industrial Mathematics|language=en|volume=8|issue=3|pages=329–336|doi=10.1134/S1990478914030041|s2cid=96437935|issn=1990-4797}}</ref>
 
 
== यह भी देखें ==
== यह भी देखें ==


* परोपकारी गतिशील कार्यक्रम, जो एक एफपीटीएएस को स्वीकार करते हैं, एक विकासवादी एल्गोरिदम को भी स्वीकार करते हैं।<ref>{{Cite journal|last1=Doerr|first1=Benjamin|last2=Eremeev|first2=Anton|last3=Neumann|first3=Frank|last4=Theile|first4=Madeleine|last5=Thyssen|first5=Christian|date=2011-10-07|title=विकासवादी एल्गोरिदम और गतिशील प्रोग्रामिंग|journal=Theoretical Computer Science|language=en|volume=412|issue=43|pages=6020–6035|doi=10.1016/j.tcs.2011.07.024|issn=0304-3975|doi-access=free}}</ref>
* "बेनिवॉलेंट डायनेमिक प्रोग्राम", जो एक एफपीटीएएस को स्वीकार करते हैं, उन्हें एक विकासात्मक एल्गोरिदम भी स्वीकार करता है।<ref>{{Cite journal|last1=Doerr|first1=Benjamin|last2=Eremeev|first2=Anton|last3=Neumann|first3=Frank|last4=Theile|first4=Madeleine|last5=Thyssen|first5=Christian|date=2011-10-07|title=विकासवादी एल्गोरिदम और गतिशील प्रोग्रामिंग|journal=Theoretical Computer Science|language=en|volume=412|issue=43|pages=6020–6035|doi=10.1016/j.tcs.2011.07.024|issn=0304-3975|doi-access=free}}</ref>
 
 
== संदर्भ ==
== संदर्भ ==
{{Reflist}}
{{Reflist}}
Line 175: Line 170:
== बाहरी संबंध ==
== बाहरी संबंध ==


* Complexity Zoo: [https://complexityzoo.net/Complexity_Zoo:F#fptas FPTAS]
* Complexity Zoo: [https://complexityzoo.net/Complexity_Zoo:F#fptas एफपीटीएएस]
[[Category: सन्निकटन एल्गोरिदम]] [[Category: जटिलता वर्ग]]  
[[Category: सन्निकटन एल्गोरिदम]] [[Category: जटिलता वर्ग]]  



Revision as of 12:15, 16 August 2023

पूर्ण बहुपद-काल सन्संवृतन प्रणाली (फुल्ली पॉलिनोमियल-टाइम अप्प्रोक्सिमशन स्कीम, एफपीटीएएस) एक ऐल्गोरिथ्म होता है जिसका उद्देश्य फंक्शन समस्याओं, विशेषकर इष्टमीकरण समस्याओं, के आपूर्तिकरण हल के आस-पास हल ज्ञात करना होता है। एफपीटीएएस को समस्या का एक दृष्टांत और पैरामीटर ε > 0 के रूप में इनपुट प्राप्त होता है। यह यथार्थ मान (वैल्यू) का कम से कम गुना और अधिकतम गुना देता है, जो कि यथार्थ मान से होते हैं।

इष्टमीकरण समस्याओं के संदर्भ में, यथार्थ मान को विकल्प समाधान के मान के रूप में समझा जाता है, और यह प्रायः इस संदर्भ में समझा जाता है कि एफपीटीएएस को एक मान्य समाधान प्रस्तुत करना चाहिए (और केवल समाधान का मान नहीं)। एक मान प्रस्तुत करना और उस मान के साथ समाधान प्राप्त करना उस समस्या की स्व-पुनर्निर्धारणीयता का अभिवादन करते हुए समान होते हैं।

महत्वपूर्ण यह है कि एफपीटीएएस के रनटाइम समस्या के आकार और 1/ε में बहुपद होता है। यह एक सामान्य बहुपद-काल सन्संवृतन प्रणाली (पॉलिनोमियल-टाइम अप्प्रोक्सिमशन स्कीम, पीटीएएस) के विपरीत है। सामान्य PTAS का रन-टाइम प्रत्येक विशिष्ट ε के लिए समस्या आकार में बहुपद है, लेकिन 1/ε में घातांकीय हो सकता है।[1]

एफपीटीएएस शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक एफपीटीएएस हो। एफपीटीएएस पीटीएएस की एक उपसमुच्चय है, और जब तक P = NP नहीं हो, यह एक सख्त उपसमुच्चय है।[2]

अन्य कम्प्लेक्सिटी वर्गों से संबंध

एफपीटीएएस में सभी समस्याएं मानक पैरामीटरीकरण के संबंध में निश्चित-पैरामीटर पर आधारित हैं।[3]

बहुपद से परिबद्ध (बाउंडेड) उद्देश्य फलन के साथ किसी भी दृढ़ NP-हार्ड अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि P=NP नहीं।[4] हालाँकि, प्रतिवर्ती नहीं होता: उदाहरण स्वरूपन, यदि P, NP से बराबर नहीं है, तो डोरा में दो प्रतिबंधों के साथ यह स्थिरता दृढ़ NP-हार्ड नहीं है, लेकिन जब तक इष्टतम उद्देश्य बहुपद परिबद्ध नहीं हो, तो उसका कोई एफपीटीएएस नहीं है।[5]

डायनामिक प्रोग्राम को एफपीटीएएस में परिवर्तित करना

वेगिंगर[6] ने एक ऐसे विशेष श्रेणी के डायनामिक प्रोग्रामिंग को एक एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की।

इनपुट

यह योजना उन इष्टमीकरण समस्याओं को हैंडल करती है जिनमें इनपुट निम्नलिखित तरीके से परिभाषित होता है:

  • इनपुट n सदिशों, x1,...,xn से बना होता है।
  • प्रत्येक इनपुट सदिश किसी गैर-नकारात्मक पूर्णांकों से बना होता है, जहाँ इनपुट पर निर्भर कर सकता है।
  • इनपुट सदिशों के सभी घटक बाइनरी में एनकोड होते हैं। इसलिए समस्या का आकार O(n+log(X)) होता है, जहाँ X सभी सदिशों के सभी घटकों की योग है।

अत्यंत सरल डायनामिक प्रोग्राम

माना जाता है कि समस्या में एक डायनामिक-प्रोग्रामिंग (डीपी) एल्गोरिथ्म होता है जो स्थितियों का उपयोग करता है। प्रत्येक स्थिति एक ऐसा सदिश होता है जिसमें कुछ गैर-नकारात्मक पूर्णांक होते हैं, जहाँ इनपुट से अनबद्ध होता है। डीपी n चरणों में काम करता है। प्रत्येक चरण i पर, यह इनपुट xi को प्रोसेस करता है और स्थितियों का एक समुच्चय Si बनाता है। प्रत्येक स्थिति एक अधिंश समस्या को एनकोड करती है, x1,...,xi का उपयोग करके। डीपी के घटक हैं:

  • एक प्रारंभिक स्थितियों का समुच्चय S0
  • परिवर्ती फलन का समुच्चय F। प्रत्येक फलन f, F में एक युग्म (स्थिति, इनपुट) को एक नई स्थिति में मान देता है।
  • एक उद्देश्य फलन g, जो स्थिति को उसके मूल्य में मान देता है।

डीपी का एल्गोरिदम है:

  • मान लीजिए S0 := प्रारंभिक अवस्थाओं का समुच्चय।
  • k = 1 से n के लिए करें:
    • समुच्चय Sk := {f(s,xk) | f in F, s in Sk−1}
  • आउटपुट न्यूनतम/अधिकतम {g(s) | s in Sn}।

डायनैमिक प्रोग्रामिंग का रनटाइम संभावित स्थितियों की संख्या में लीनियर होता है। सामान्यत: इस संख्या का आकार इनपुट समस्या के आकार में घातांकीय हो सकता है: यह O(n Vb) में हो सकता है, जहाँ V एक स्थिति में प्रकट होने वाले सबसे बड़े पूर्णांक है। यदि V, O(X) में है, तो रनटाइम O(n Xb) में होता है, जो कि केवल प्यूडो-बहुपद समय होता है, क्योंकि यह समस्या के आकार में घातांकीय होता है जो O(log X) में होता है।

इसे बहुपद बनाने का एक तरीका है स्थिति-स्थान को ट्रिम करें: प्रत्येक चरण में संभावित स्थितियों को सब नहीं रखने की जगह, केवल स्थितियों का एक उपसमुच्चय रखने की जगह; उन स्थितियों को हटा दें जो अन्य स्थितियों के "पर्याप्त रूप से संवृत" हैं। निश्चित स्थितियों की यह कट कुछ शर्तों के अधीन की जा सकती है, जिनके अधीन यह किसी स्थिति की उच्चता मान में बहुत अधिक बदलाव नहीं लाता है।

इसे औपचारिकत: इसे हम मानते हैं कि समस्या के पास एक गैर-नकारात्मक पूर्णांक सदिश d = (d1,...,db) है, जिसे समस्या का डिग्री सदिश कहा जाता है। प्रत्येक वास्तविक संख्या r>1 के लिए, हम कहते हैं कि दो स्थिति-सदिश s1,s2 (d,r)-संवृत हैं यदि, प्रत्येक समन्वय j, 1,...,b तक: (विशेषकर, यदि किसी j के लिए dj=0 है, तो )।

कोई समस्या अत्यंत कल्याणकारी कहलाती है यदि वह निम्नलिखित तीन शर्तों को पूरा करती हो:

  1. परिवर्ती फलन द्वारा सामीप्यता (प्रॉक्सिमिटी) संरक्षित रहती है: किसी भी r>1 के लिए, किसी भी संक्रमण फलन f, F में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिशों s1,s2 के लिए, निम्नलिखित सत्य है: यदि s1 s2 के लिए (d, r)-संवृत है, तो f(s1, x) f(s2, x) के लिए (d, r)-संवृत है।
    • इसके लिए एक पर्याप्त शर्त को निम्नलिखित रूप में जांचा जा सकता है। प्रत्येक फलन f(s, x), F में, और प्रत्येक निर्देशांक j, 1,...,b तक, f की jवीं निर्देशांक को fj(s,x) के रूप में दर्शाया जा सकता है। यह fj को b+a चरणों में एक पूर्णांक फलन के रूप में देखा जा सकता है। मान लीजिए कि प्रत्येक ऐसे fj एक ऐसा बहुपद है जिसमें गैर-नकारात्मक संख्यात्मक हैं। इसे z में एकल पूर्णांक के बहुपद में बदलें, s=(zd1,...,zdb) और x=(1,...,1) को विकल्प करके। यदि परिणामक बहुपद का डिग्री z में अधिक से अधिक dj है, तो शर्त 1 पूरी होती है।
  2. मूल्य फलन द्वारा संवृत का संरक्षित रहना: एक पूर्णांक G ≥ 0 मौजूद है (जो मूल्य फलन g और डिग्री सदिश d का एक फलन है), ऐसा कि किसी भी r>1, और किसी भी दो स्थिति-सदिशों s1,s2 के लिए, निम्नलिखित सत्य है: यदि s1 s2 के लिए (d, r)-संवृत है, तो: g(s1) ≤ rG · g(s2) (न्यूनीकरण समस्याओं में); g(s1) ≥ r(-G) · g(s2) (अधिकतमीकरण समस्याओं में)।
    • इसके लिए पर्याप्त शर्त यह है कि फलन g एक बहुपद फलन (b वेरिएबल की) हो, जिसमें गैर-नकारात्मक संख्यात्मक हों।
  3. तकनीकी शर्तें:
    • सभी संक्रमण फलन f, F और मूल्य फलन g को पॉलिटाइम में मूल्यांकित किया जा सकता है।
    • परिवर्ती फलन की संख्या |F|, n और log(X) में बहुपद है।
    • प्रारंभिक स्थितियों का समुच्चय S0 को n और log(X) में बहुपद समय में गणना की जा सकती है।
    • Vj को स्थिति के निर्देशांक j में प्रकट होने वाले सभी मानों का समुच्चय कहें। तब, Vj में प्रत्येक मान का ln न केवल एक बहुपद P1(n,log(X)) में सबसे अधिक है।
    • यदि dj=0, तो Vj की कार्डिनैलिटी न केवल एक बहुपद P2(n,log(X)) में सबसे अधिक हो सकती है।

प्रत्येक अत्यधिक बेनिवॉलेंट समस्या के लिए, डायनामिक कार्यक्रम को एक एफपीटीएएस में परिवर्तित किया जा सकता है। निर्धारित करें:

  • := आवश्यक सन्संवृतन अनुपात।
  • , जहां G स्थिति 2 से स्थिरांक है। ध्यान दें .
  • , जहाँ P1 स्थिति 3 से बहुपद है (प्रत्येक मान के ln पर ऊपरी सीमा जो एक स्थिति सदिश में दिखाई दे सकती है)। ध्यान दें कि , इसलिए यह इनपुट के आकार में और में बहुपद है। साथ ही, , इसलिए P1 की परिभाषा के अनुसार, प्रत्येक पूर्णांक जो एक स्थिति-सदिश में दिखाई दे सकता है वह सीमा [0,rL] में है।
  • सीमा [0,rL] को L+1 r-अंतरालों में विभाजित करें:
  • स्थिति समष्टि को r-बॉक्स में विभाजित करें: प्रत्येक निर्देशिका k जिसका डिग्री dk ≥ 1 है, विशीर्णता ऊपर L+1 अंतरालों में विभाजित किया जाता है; प्रत्येक निर्देशिका जिसका dk = 0 है, P2(n,log(X)) एकल अंतरालों में विभाजित किया जाता है - प्रत्येक संभावित मूल्य के लिए एक अंतराल (जहां P2 उपरोक्त शर्त 3 से बहुपद है)।
    • ध्यान दें कि प्रत्येक संभावित स्थिति केवल r-बॉक्स में सम्मिलित है; यदि दो स्थितियाँ एक ही r-बॉक्स में हैं, तो वे (d,r)-संवृत हैं।
  • .
    • ध्यान दें कि r-बॉक्स की संख्या अधिकतम R है। क्योंकि b एक निश्चित स्थिर संख्या है, इसलिए यह R इनपुट के आकार में बहुपद और में है।

एफपीटीएएस डीपी के समान ढंग से चलता है, लेकिन प्रत्येक चरण में, यह स्थिति समुच्चय को एक छोटे समुच्चय Tk में काटता है, जो प्रत्येक r-बॉक्स में एक ही स्थिति को सम्मिलित करता है। एफपीटीएएस की एल्गोरिथम निम्नलिखित है:

  • मान लीजिए T0  := S0 = प्रारंभिक अवस्थाओं का समुच्चय।
  • k = 1 से n के लिए करें:
    • मान लीजिए Uk := {f(s,xk) | f in F, s in Tk−1}
    • मान लीजिए Tk := Uk की एक संक्षिप्त प्रति: प्रत्येक r-बॉक्स के लिए जिसमें Uk के एक या अधिक राज्य हैं, Tk में ठीक एक स्थिति रखें।
  • आउटपुट न्यूनतम/अधिकतम {g(s) | s in Tn}।

एफपीटीएएस का रनटाइम प्रत्येक Ti में संभावित स्थितियों की कुल संख्या में बहुपद होता है, जो अधिकतम एकत्रित r-बॉक्स की कुल संख्या होती है, जो अधिकतम R होती है, जो बहुपद होती है n, log(X), और में।

ध्यान दें कि प्रत्येक स्थिति su में Uk में, उसका उपसमुच्चय Tk में कम से कम एक स्थिति st होता है जो su के (d, r)-संवृत होता है। भी, प्रत्येक Uk प्रारंभिक (बिना काटे गए) डीपी के स्थिति समुच्चय Sk की एक उपसमुच्चय है। एफपीटीएएस की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:[6]: Lem.3.3 

प्रत्येक चरण k में 0,...,n, प्रत्येक स्थिति ss Sk में, एक ऐसी स्थिति st होती है जो ss के (d,rk)-संवृत होती है।

इसका प्रमाण k पर प्रेरण द्वारा है। k=0 के लिए हमारे पास Tk=Sk है; प्रत्येक अवस्था (d,1)-स्वयं के संवृत है। मान लीजिए कि लेम्मा k-1 के लिए धारण करता है। Sk में प्रत्येक अवस्था ss के लिए, ss- को Sk-1 में अपने पूर्ववर्तियों में से एक होने दें, ताकि f(ss−,x)=ss। प्रेरण धारणा के अनुसार, Tk-1 में एक अवस्था st - है, अर्थात (d,rk-1)-ss− के संवृत। चूंकि संवृत संक्रमणों (उपरोक्त शर्त 1) द्वारा संरक्षित है, f(st−,x) (d,rk-1)-f(ss−,x)=ss के संवृत है। यह f(st−,x) यूके में है। ट्रिमिंग के बाद, Tk में एक अवस्था st होती है जो कि (d,r)-f(st-,x) के संवृत होती है। यह सेंट (d,rk)-ss के संवृत है।

अब विचार करें कि स्थिति s*, Sn में है, जो सर्वोत्तम समाधान का संवादना करती है (अर्थात, g(s*)=OPT)। उपरोक्त उपनिवेश के अनुसार, एक स्थिति t*, Tn में है, जो s* के (d,rn)-संवृत है। संवृत मूल्य फलन द्वारा संरक्षित होती है, इसलिए एक अधिकतमीकरण समस्या के लिए g(t*) ≥ r(-Gn) · g(s*) होता है। r की परिभाषा द्वारा, । इस प्रकार होता है। एक समान तर्क एक न्यूनीकरण समस्या के लिए काम करता है।

उदाहरण

यहां अत्यंत-बेनिवॉलेंट समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।[6]

1. मल्टीवे संख्या संविभाजन (समान-मशीन शेड्यूलिंग के साथ व्यक्तिगत करने की अभिलाषा के साथ) जिसका लक्ष्य सबसे बड़ी योग को कम करना है, बेहद बेनिवॉलेंट है। यहां, हमारा a = 1 होता है (इंटीज होते हैं), और b = बिनों की संख्या (जिसे स्थिर माना जाता है)। प्रत्येक स्थिति b योगों की बिनों के योगों का प्रतिनिधित्व करने वाले b पूर्णांकों का एक सदिश होती है। यहाँ b की फलन होती हैं: प्रत्येक फलन j अगले इंटीज को बिन j में डालने का प्रतिनिधित्व करती है। फलन g(s), s के सबसे बड़े तत्व को चुनती है। S0 = {(0,...,0)}। बेनिवॉलेंट के शर्त d=(1,...,1) और G=1 के साथ पूरी होती है। यह परिणाम समान मशीन अनुसूची और असंबद्ध मशीन अनुसूची में विस्तार पाता है जब मशीनों की संख्या स्थिर होती है (यह इसलिए आवश्यक है क्योंकि R - r-बॉक्सों की अधिकतम संख्या - b में घनात्मक होती है)। Pm|| या Qm|| या Rm|| कहा जाता है।

  • ध्यान दें: एक विशेष प्रकार की स्थिति b=2 को विचार करें, जहाँ लक्ष्य दो भागों के योग के बीच अंतर के वर्ग को कम करना है। एक ही डीपी का उपयोग किया जा सकता है, लेकिन इस बार मूल्य फलन g(s) = (s1-s2)2 के साथ, जहाँ s1 और s2 दो भागों के योग होते हैं। अब, शर्त 2 का उल्लंघन होता है: स्थितियाँ (s1,s1) और (s1,s2) (d,r)-संवृत हो सकती हैं, लेकिन g(s1,s1) = 0 होता है जबकि g(s1,s2) > 0 होता है। इस प्रकार, उपरोक्त सिद्धांत का लागू नहीं हो सकता है। यद्यपि, समस्या के पास एफपीटीएएस नहीं होता है जब तक P=NP नहीं होता है, क्योंकि एफपीटीएएस का पॉलिटाइम में उपयोग करके निर्णय किया जा सकता है कि श्रेष्ठ मूल्य 0 है या नहीं।

2. समान या समान मशीनों की किसी भी निश्चित संख्या पर घन कार्य पूरा होने के समय का योग - Qm|| द्वारा निरूपित बाद वाला - a=1, b=3, d=(1,1,3) के साथ पूर्व-बेनिवॉलेंट है। इसे पूर्ण होने के समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।

3. समान या समान मशीनों की किसी भी निश्चित संख्या पर भारित समापन समय का योग - बाद वाले को Qm|| द्वारा दर्शाया गया है।

4. समय-निर्भर प्रसंस्करण समय के साथ, समान या समान मशीनों की किसी भी निश्चित संख्या पर पूरा होने के समय का योग: Qm|time-dep|। यह पूरा होने के समय के भारित योग के लिए भी लागू है।

5. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: m||

सरल डायनामिक कार्यक्रम

सरल डायनामिक प्रोग्राम उपरोक्त फॉर्मूलेशन में निम्नलिखित घटक जोड़ते हैं:

  • एक फ़िल्टरिंग फलनों का समुच्चय H, जो F की तरही संख्या में होते हैं। प्रत्येक फलन hi, H में एक युग्म (स्थिति, इनपुट) को एक बूलियन मूल्य में चित्रित करती है। मूल्य "सत्य" तभी होना चाहिए जब और केवल जब इस जोड़ पर fi का संक्रमण किया जाएगा और यह एक मान्य स्थिति तक पहुँचाएगा।
  • एक प्रदर्शन संबंध, जो स्थितियों पर एक आंशिक आदेश है (कोई समानता नहीं, सभी जोड़ों का तुलना किया नहीं जा सकता है), और एक अर्ध-प्रदर्शन संबंध, जो स्थितियों पर एक पूर्ण पूर्व-क्रम है (समानताएँ अनुमति दी जाती हैं, सभी जोड़ों की तुलना की जा सकती है)।

मूल डीपी को इस प्रकार संशोधित किया गया है:

  • मान लीजिए S0 := प्रारंभिक अवस्थाओं का समुच्चय।
  • k = 1 से n के लिए करें:
    • मान लीजिए Sk := {fj(s,xk) | fj in F, s in Sk−1, hj(s,xk)=True }, जहां hj ट्रांज़िशन फलन fj के अनुरूप फ़िल्टर फलन है।
  • आउटपुट का न्यूनतम/अधिकतम {g(s) | s in Sn}।

एक समस्या को बेनिवॉलेंट कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो ऊपर दी गई शर्तों 1, 2, 3 को विस्तारित करती हैं):

  1. प्राक्षिपत्ति परियोजनाओं द्वारा संरक्षित की जाती है: किसी भी r>1 के लिए, किसी भी परियोजना फलन f, F में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिश s1,s2 के लिए, निम्नलिखित सत्य है:
    • यदि s1, s2 के प्रति (d,r)-संवृत है, s1, s2 को क्वासी-डॉमिनेट करता है, तो या तो (a) f(s1,x) f(s2,x) के प्रति (d,r)-संवृत है, और f(s1,x) f(s2,x) को क्वासी-डॉमिनेट करता है, या (b) f(s1,x) f(s2,x) को डॉमिनेट करता है।
    • यदि s1 s2 को डॉमिनेट करता है, तो f(s1,x) f(s2,x) को डॉमिनेट करता है।
  2. मूल्य फलन द्वारा प्राक्षिपत्ति संरक्षित की जाती है: एक पूर्णांक G ≥ 0 (मान फलन g और डिग्री सदिश d का एक फलन) विद्यमान है, जैसे कि किसी भी r>1 के लिए, और किसी भी दो स्थिति-सदिश s1,s2 के लिए, निम्नलिखित धारण करता है:
    • यदि s1 s2 के प्रति (d,r)-संवृत है, और s1 s2 को क्वासी-डॉमिनेट करता है, तो: g(s1) ≤ rG · g(s2) (न्यूनतमीकरण समस्याओं में); g(s1) ≥ r(-G) · g(s2) (अधिकतमीकरण समस्याओं में)।
    • यदि s1 s2 को डॉमिनेट करता है, तो: g(s1) ≤ g(s2) (न्यूनतमीकरण समस्याओं में); g(s1) ≥ g(s2) (अधिकतमीकरण समस्याओं में)।
  3. तकनीकी शर्तें (उपरोक्त के अतिरिक्त):
    • क्वासी-डॉमिनेटता संबंध को बिनोमिक समय में तय किया जा सकता है।
  4. फ़िल्टर फलनों पर शर्तें: किसी भी r>1 के लिए, किसी भी फ़िल्टर फलन h, H में, किसी भी इनपुट-सदिश x के लिए, और किसी भी दो स्थिति-सदिश s1,s2 के लिए, निम्नलिखित सत्य है:
    • यदि s1 s2 के प्रति (d,r)-संवृत है, और s1 s2 को क्वासी-डॉमिनेट करता है, तो h(s1,x) ≥ h(s2,x)
    • यदि s1 s2 को डॉमिनेट करता है, तो h(s1,x) ≥ h(s2,x)।

प्रत्येक बेनिवॉलेंट समस्या के लिए, डायनेमिक प्रोग्राम को उसी तरीके से एक एफपीटीएएस में बदला जा सकता है जैसा कि ऊपर वाले में किया गया है, दो परिवर्तनों (निर्भीक) के साथ:

  • मान लीजिए T0 := S0 = प्रारंभिक अवस्थाओं का समुच्चय।
  • k = 1 से n के लिए करें:
    • मान लीजिए Uk := {fj(s,xk) | fj in F, s in Tk−1, hj(s,xk)=True }, जहां hj संक्रमण फलन fj के अनुरूप फ़िल्टर फलन है।
    • मान लीजिए Tk := Uk की एक छंटनी की गई प्रति: प्रत्येक r-बॉक्स के लिए जिसमें Uk के एक या अधिक स्थिति सम्मिलित हैं, एक एकल तत्व चुनें जो Uk में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता है, और इसे Tk में डालें।
  • आउटपुट का न्यूनतम/अधिकतम {g(s) | s in Tn}।

उदाहरण

यहां बेनिवॉलेंट समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।[6]

1. 0-1 नैपसैक समस्या बेनिवॉलेंट है। यहाँ, a=2 है: प्रत्येक इनपुट एक 2-सदिश (वेट, मूल्य) होता है। हमारे पास b=2 है: प्रत्येक स्थिति (वर्तमान वेट, वर्तमान मूल्य) को कोड करती है। दो परियोजना फलन होते हैं: f1 अगले इनपुट आइटम को जोड़ने का संदर्भ देता है, और f2 उसे नहीं जोड़ने का। उसके संबंधित फ़िल्टर फलन हैं: h1 यह सत्यापित करता है कि अगले इनपुट आइटम का वेट किन्नर क्षमता से कम है; h2 हमेशा सच की वापसी करता है। मूल्य फलन g(s) s2 को वापसी करता है। प्रारंभिक स्थिति-समुच्चय है {(0,0)}। डिग्री सदिश (1,1) है। डॉमिनेट संबंध घटित है। क्वासी-डॉमिनेटता संबंध केवल वेट समन्वय करता है: s ने तीव्रीक संबंध है तब t का वेट t1 से कम या बराबर होता है। इसका अर्थ है कि, यदि स्थिति t का स्थिति s से अधिक वेट है, तो परियोजना फलनों को तकनीकी रूप से t और s के बीच समर्पण को संरक्षित नहीं करने की अनुमति है (यह संभव है, उदाहरणार्थ, कि s के एक सफलता कारक है और t का उसके समर्पक का उपयुक्त सफलता कारक नहीं है)। एक समान एल्गोरिथ्म पहले Ibarra और Kim ने प्रस्तुत किया था।[7] इस एफपीटीएएस की रनटाइम को पूर्णांकों पर क्रियाएँ करने के लिए सुधारा जा सकता है।[8] गुणक पश्चात्तल में 2.5 तक सुधारा गया था।[9]

  • नोट: 2-वेटेड नैपसैक समस्या में, जहाँ प्रत्येक आइटम के दो वेट और एक मूल्य होता है, और लक्ष्य होता है कि विल्यू बढ़ाएं ताकि कुल वेट के वर्गों का योग किन्नर क्षमता से कम या बराबर हो: । हम इसे एक समान डीपी का उपयोग करके हल कर सकते हैं, जहाँ प्रत्येक स्थिति (वर्तमान वेट 1, वर्तमान वेट 2, मूल्य) होती है। क्वासी-डॉमिनेटता संबंध को बदलकर किया जाना चाहिए: s तीव्रीक तो t iff (s12 + s22) ≤ (t12 + t22)। लेकिन यह शर्त 1 का उल्लंघन करता है: क्वासी-डॉमिनेटता संबंध संक्रिया फलन द्वारा संरक्षित नहीं किया जाता है, उदाहरण के लिए, स्थिति (2,2,..) (1,3,..) को क्वासी-डॉमिनेटता करती है; लेकिन उसके बाद जब इनपुट (2,0,..) को दोनों स्थितियों में जोड़ते हैं, परिणाम (4,2,..) (3,3,..) को क्वासी-डॉमिनेटता नहीं करता है। इसलिए यह सिद्धांत का उपयोग नहीं किया जा सकता है। वास्तव में, यह समस्या एफपीटीएएस नहीं है जब तक P=NP नहीं हो। ऐसा ही दो-विमीय नैपसैक समस्या के लिए भी है। ऐसा ही एकाधिक उपसमुच्चय समस्या के लिए भी है: क्वासी-डॉमिनेटता संबंध इस तरह होना चाहिए: s तीव्रीक तो t iff max(s1,s2) ≤ max(t1,t2), लेकिन यह संक्रियाओं द्वारा संरक्षित नहीं किया जाता है, उपर दिए गए उदाहरण की तरह।

2. एकल मशीन पर टार्डी जॉब्स की वेटेड संख्या को कम करने के लिए, या अलगाव जॉब्स की वेटेड संख्या को बढ़ाने के लिए; चिह्नित 1||

3. वफसवान जॉब्स की वेटेड संख्या को कम करने के लिए बैच अनुसूचना: 1|बैच|

4. एकल मशीन पर डेटेरियरेटिंग जॉब्स की मेक्सपैन: 1|डिटीरियोरेट|

5. एकल मशीन पर कार्य में विलंब: 1||

6. एकल मशीन पर कुल वेटेड कार्य में विलंब: 1||

गैर-उदाहरण

उपरोक्त परिणाम की व्यापकता के बावजूद, ऐसे ऐसी स्थिति हैं जहां इसका उपयोग नहीं किया जा सकता है।

1. कुल टार्डिनेस समस्या 1|| में, लॉलर[10] के डायनेमिक प्रोग्रामिंग सूत्र को अपडेट करने की आवश्यकता होती है, जिसमें पुराने स्थिति स्थान के सभी स्थितियों को कुछ B बार अपडेट किया जाता है, जहाँ B, X (अधिकतम इनपुट आकार) के आदर्श में होता है। यही समान ब्यवहार आर्थिक लॉट-साइजिंग के लिए डीपी के लिए भी होता है।[11] इन स्थितियों में, F में परियोजना फलनों की संख्या B होती है, जो लॉग(X) में अपेक्षित होती है, इसलिए दूसरी तकनीकी शर्त का उल्लंघन हो जाता है। स्थिति-काटन तकनीक उपयोगी नहीं होती है, लेकिन एक दूसरी तकनीक - इनपुट-राउंडिंग - का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।[12][13]

2. वैरिएंस मिनिमाइजेशन समस्या 1|| में, उद्देश्य फलन है, जो शर्त 2 का उल्लंघन करता है, इसलिए सिद्धांत का उपयोग नहीं किया जा सकता है। लेकिन विभिन्न तकनीकों का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।[14][15]

कुछ अन्य समस्याएं जिनमें एफपीटीएएस है

  • नैपसेक समस्या,[16][17] साथ ही इसके कुछ प्रकार:
    • 0-1 नैपसेक समस्या।[18]
    • अनपरिबद्ध नैपसैक समस्या।[19]
    • डेल्टा-मॉड्यूलर बाधाओं के साथ बहुविमीय नैपसेक समस्या।[20]
    • बहुउद्देश्यीय 0-1 नैपसेक समस्या।[21]
    • पैरामीट्रिक नैपसेक समस्या।[22]
    • सममित द्विघात नैपसेक समस्या।[23]
  • गणना-उपसमुच्चय-योग (#उपसमुच्चय योग समस्या) - अधिकतम सी के योग के साथ अलग-अलग उपसमुच्चय की संख्या ज्ञात करना।[24]
  • प्रतिबंधित सबसे छोटा पथ समस्या: विलंब बाधा के अधीन, ग्राफ़ में दो नोड्स के बीच न्यूनतम लागत वाला पथ ढूंढना।[25]
  • सबसे छोटे रास्ते और गैर-रैखिक उद्देश्य।[26]
  • एज-कवर की गणना[27]
  • सदिश उपसमुच्चय खोज समस्या जहां विमा निश्चित है।[28]

यह भी देखें

  • "बेनिवॉलेंट डायनेमिक प्रोग्राम", जो एक एफपीटीएएस को स्वीकार करते हैं, उन्हें एक विकासात्मक एल्गोरिदम भी स्वीकार करता है।[29]

संदर्भ

  1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial optimization problems and their approximability properties, Springer-Verlag, 1999.
  2. Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. See discussion following Definition 1.30 on p. 20.
  3. Cai, Liming; Chen, Jianer (June 1997). "फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर". Journal of Computer and System Sciences (in English). 54 (3): 465–474. doi:10.1006/jcss.1997.1490.
  4. Vazirani, Vijay V. (2003). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.
  5. H. Kellerer; U. Pferschy; D. Pisinger (2004). बस्ता समस्याएँ. Springer.
  6. 6.0 6.1 6.2 6.3 Woeginger, Gerhard J. (2000-02-01). "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?". INFORMS Journal on Computing. 12 (1): 57–74. doi:10.1287/ijoc.12.1.57.11901. ISSN 1091-9856.
  7. Ibarra, Oscar H.; Kim, Chul E. (1975-10-01). "नैपसैक और सबसेट समस्याओं के योग के लिए तेज़ सन्निकटन एल्गोरिदम". Journal of the ACM. 22 (4): 463–468. doi:10.1145/321906.321909. ISSN 0004-5411. S2CID 14619586.
  8. Lawler, Eugene L. (1979-11-01). "नैपसेक समस्याओं के लिए तेज़ सन्निकटन एल्गोरिदम". Mathematics of Operations Research. 4 (4): 339–356. doi:10.1287/moor.4.4.339. ISSN 0364-765X. S2CID 7655435.
  9. Rhee, Donguk (2015). नैपसैक समस्याओं के लिए तेज़ पूर्णतः बहुपद सन्निकटन योजनाएँ (Thesis thesis). Massachusetts Institute of Technology. hdl:1721.1/98564.
  10. Lawler, Eugene L. (1977-01-01), Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), "A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X", Annals of Discrete Mathematics, Studies in Integer Programming (in English), Elsevier, vol. 1, pp. 331–342, doi:10.1016/S0167-5060(08)70742-8, retrieved 2021-12-17
  11. Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980-07-01). "Deterministic Production Planning: Algorithms and Complexity". Management Science. 26 (7): 669–679. doi:10.1287/mnsc.26.7.669. ISSN 0025-1909.
  12. Lawler, E. L. (1982-12-01). "संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना". Operations Research Letters (in English). 1 (6): 207–208. doi:10.1016/0167-6377(82)90022-0. ISSN 0167-6377.
  13. van Hoesel, C. P. M.; Wagelmans, Albert (1997-01-01). "एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं" (in English). {{cite journal}}: Cite journal requires |journal= (help)
  14. Cai, X. (1995-09-21). "एकल मशीन प्रणालियों में सहमत रूप से भारित विचरण को न्यूनतम करना". European Journal of Operational Research (in English). 85 (3): 576–592. doi:10.1016/0377-2217(93)E0367-7. ISSN 0377-2217.
  15. Woeginger, Gerhard J. (1999-05-01). "एक ही मशीन पर सहमत रूप से भारित भिन्नता को न्यूनतम करने के लिए एक अनुमान योजना". INFORMS Journal on Computing. 11 (2): 211–216. doi:10.1287/ijoc.11.2.211. ISSN 1091-9856.
  16. Vazirani, Vijay (2001). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 69–70. ISBN 3540653678. OCLC 47097680.
  17. Kellerer, Hans; Pferschy, Ulrich (2004-03-01). "नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग". Journal of Combinatorial Optimization (in English). 8 (1): 5–11. doi:10.1023/B:JOCO.0000021934.29833.6b. ISSN 1573-2886. S2CID 36474745.
  18. Jin, Ce (2019). 0-1 नैपसेक के लिए एक बेहतर एफपीटीएएस. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 132. pp. 76:1–76:14. arXiv:1904.09562. doi:10.4230/LIPIcs.ICALP.2019.76. ISBN 9783959771092. S2CID 128317990.
  19. Jansen, Klaus; Kraft, Stefan E. J. (2018-02-01). "अनबाउंडेड नैपसैक समस्या के लिए एक तेज़ एफपीटीएएस". European Journal of Combinatorics. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller (in English). 68: 148–174. arXiv:1504.04650. doi:10.1016/j.ejc.2017.07.016. ISSN 0195-6698. S2CID 9557898.
  20. Gribanov, D. V. (2021-05-10). "An FPTAS for the $$\var Delta $$-Modular Multidimensional Knapsack Problem". गणितीय अनुकूलन सिद्धांत और संचालन अनुसंधान. Lecture Notes in Computer Science. Vol. 12755. pp. 79–95. arXiv:2103.07257. doi:10.1007/978-3-030-77876-7_6. ISBN 978-3-030-77875-0. S2CID 232222954.
  21. Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01). "Implementing an efficient fptas for the 0–1 multi-objective knapsack problem". European Journal of Operational Research (in English). 198 (1): 47–56. doi:10.1016/j.ejor.2008.07.047. ISSN 0377-2217.
  22. Holzhauser, Michael; Krumke, Sven O. (2017-10-01). "पैरामीट्रिक नैपसेक समस्या के लिए एक एफपीटीएएस". Information Processing Letters (in English). 126: 43–47. arXiv:1701.07822. doi:10.1016/j.ipl.2017.06.006. ISSN 0020-0190. S2CID 1013794.
  23. Xu, Zhou (2012-04-16). "सममित द्विघात नैपसैक समस्या के लिए एक प्रबल बहुपद FPTAS". European Journal of Operational Research (in English). 218 (2): 377–381. doi:10.1016/j.ejor.2011.10.049. ISSN 0377-2217.
  24. Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (2011-10-01). "An FPTAS for #Knapsack and Related Counting Problems". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 817–826. doi:10.1109/FOCS.2011.32. ISBN 978-0-7695-4571-4. S2CID 5691574.
  25. Ergun, Funda; Sinha, Rakesh; Zhang, Lisa (2002-09-15). "प्रतिबंधित सबसे छोटे पथ के लिए एक बेहतर एफपीटीएएस". Information Processing Letters (in English). 83 (5): 287–291. doi:10.1016/S0020-0190(02)00205-3. ISSN 0020-0190.
  26. Tsaggouris, George; Zaroliagis, Christos (2009-06-01). "Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications". Theory of Computing Systems (in English). 45 (1): 162–186. doi:10.1007/s00224-007-9096-4. ISSN 1433-0490. S2CID 13010023.
  27. Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (2013-12-18), "A Simple FPTAS for Counting Edge Covers", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 341–348, arXiv:1309.6115, doi:10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID 14598468, retrieved 2021-12-13
  28. Kel’manov, A. V.; Romanchenko, S. M. (2014-07-01). "वेक्टर उपसमुच्चय खोज समस्या के लिए एक FPTAS". Journal of Applied and Industrial Mathematics (in English). 8 (3): 329–336. doi:10.1134/S1990478914030041. ISSN 1990-4797. S2CID 96437935.
  29. Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "विकासवादी एल्गोरिदम और गतिशील प्रोग्रामिंग". Theoretical Computer Science (in English). 412 (43): 6020–6035. doi:10.1016/j.tcs.2011.07.024. ISSN 0304-3975.


बाहरी संबंध