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

From Vigyanwiki
(Created page with "पूर्ण बहुपद-समय सन्निकटन योजना (एफपीटीएएस) फ़ंक्शन समस्याओं, विशे...")
 
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
पूर्ण बहुपद-समय सन्निकटन योजना (एफपीटीएएस) फ़ंक्शन समस्याओं, विशेष रूप से [[अनुकूलन समस्या]]ओं के अनुमानित समाधान खोजने के लिए एक [[कलन विधि]] है। एक FPTAS इनपुट के रूप में समस्या का एक उदाहरण और एक पैरामीटर ε > 0 लेता है। यह आउटपुट के रूप में कम से कम एक मान लौटाता है <math>1-\epsilon</math> सही मान का गुना, और अधिक से अधिक <math>1 + \epsilon</math> सही मान का गुना.
'''पूर्ण बहुपद-काल सन्संवृतन प्रणाली''' (फुल्ली पॉलिनोमियल-टाइम अप्प्रोक्सिमशन स्कीम, '''एफपीटीएएस''') एक [[कलन विधि|ऐल्गोरिथ्म]] होता है जिसका उद्देश्य फंक्शन समस्याओं, विशेषकर [[अनुकूलन समस्या|इष्टमीकरण समस्याओं]], के आपूर्तिकरण हल के आस-पास हल ज्ञात करना होता है। एफपीटीएएस को समस्या का एक दृष्टांत और पैरामीटर ε > 0 के रूप में इनपुट प्राप्त होता है। यह यथार्थ मान (वैल्यू) का कम से कम <math>1-\epsilon</math> गुना और अधिकतम <math>1 + \epsilon</math> गुना देता है, जो कि यथार्थ मान से होते हैं।


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


महत्वपूर्ण बात यह है कि एफपीटीएएस का रन-टाइम समस्या आकार और 1/ε में बहुपद है। यह सामान्य [[बहुपद-समय सन्निकटन योजना]] (पीटीएएस) के विपरीत है। सामान्य पीटीएएस का रन-टाइम प्रत्येक विशिष्ट ε के लिए समस्या आकार में बहुपद है, लेकिन 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>
एफपीटीएएस शब्द का उपयोग एफपीटीएएस वाली समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। एफपीटीएएस पीटीएएस का एक उपसमुच्चय है, और जब तक पी = एनपी समस्या नहीं है|पी = एनपी, यह एक सख्त उपसमुच्चय है।<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>
== अन्य कम्प्लेक्सिटी वर्गों से संबंध ==
एफपीटीएएस में सभी समस्याएं मानक पैरामीटरीकरण के संबंध में निश्चित-पैरामीटर पर आधारित हैं।<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-हार्ड]] अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि 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>{{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 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> हालाँकि, उलटा विफल रहता है: उदा. यदि पी, एनपी के बराबर नहीं है, तो नैपसैक समस्याओं की सूची#एकाधिक बाधाएं दृढ़ता से एनपी-हार्ड नहीं हैं, लेकिन इष्टतम उद्देश्य बहुपद रूप से बंधे होने पर भी कोई एफपीटीएएस नहीं है।<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> ने एक ऐसे विशेष श्रेणी के [[गतिशील प्रोग्रामिंग|डायनामिक प्रोग्रामिंग]] को एक एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की।
गेरहार्ड जे. वोएजिंजर<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 वैक्टर, x से बना है<sub>1</sub>,...,एक्स<sub>n</sub>.
*इनपुट ''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'' सभी सदिशों के सभी घटकों की योग है।


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


* एक सेट एस<sub>0</sub> प्रारंभिक अवस्थाओं का.
* एक ''प्रारंभिक स्थितियों'' का समुच्चय ''S''<sub>0</sub>
* संक्रमण कार्यों का एक सेट एफ। F में प्रत्येक फ़ंक्शन f एक जोड़ी (स्टेट, इनपुट) को एक नई स्थिति में मैप करता है।
* ''परिवर्ती फलन'' का समुच्चय ''F''। प्रत्येक फलन ''f,'' ''F'' में एक युग्म (स्थिति, इनपुट) को एक नई स्थिति में मान देता है।
* एक उद्देश्य फ़ंक्शन जी, एक राज्य को उसके मूल्य पर मैप करता है।
* एक उद्देश्य फलन 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) में हो सकती है<sup>b</sup>), जहां V एक राज्य में प्रदर्शित होने वाला सबसे बड़ा पूर्णांक है। यदि V, O(X) में है, तो रन-टाइम O(n X) में है<sup>b</sup>), जो केवल छद्म-बहुपद समय है, क्योंकि यह समस्या आकार में घातीय है जो O(लॉग X) में है।
डायनैमिक प्रोग्रामिंग का रनटाइम संभावित स्थितियों की संख्या में लीनियर होता है। सामान्यत: इस संख्या का आकार इनपुट समस्या के आकार में घातांकीय हो सकता है: यह O(''n V<sup>b</sup>'') में हो सकता है, जहाँ ''V'' एक स्थिति में प्रकट होने वाले सबसे बड़े पूर्णांक है। यदि ''V,'' O(''X'') में है, तो रनटाइम O(''n X<sup>b</sup>'') में होता है, जो कि केवल प्यूडो-बहुपद समय होता है, क्योंकि यह समस्या के आकार में घातांकीय  होता है जो O(log ''X'') में होता है।


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


इसे औपचारिक रूप देने के लिए, हम मानते हैं कि मौजूदा समस्या में एक गैर-नकारात्मक पूर्णांक वेक्टर d = (d) है<sub>1</sub>,...,डी<sub>b</sub>), जिसे समस्या का डिग्री वेक्टर कहा जाता है। प्रत्येक वास्तविक संख्या r>1 के लिए, हम कहते हैं कि दो राज्य-वेक्टर s हैं<sub>1</sub>,एस<sub>2</sub> हैं (d,r)-बंद करें यदि, 1,...,b में प्रत्येक निर्देशांक j के लिए: <math>r^{-d_j} \cdot s_{1,j} \leq s_{2,j} \leq r^{d_j} \cdot s_{1,j}</math> (विशेष रूप से, यदि डी<sub>j</sub>=0 कुछ j के लिए, तो <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'' के लिए, और किन्हीं दो राज्य-वेक्टर ''s'' के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है: यदि एस<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>, फिर f(s<sub>1</sub>,x) (d,r)-f(s) के करीब है<sub>2</sub>,एक्स)
# ''परिवर्ती फलन द्वारा सामीप्यता (प्रॉक्सिमिटी) संरक्षित रहती है'': किसी भी ''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 में प्रत्येक फ़ंक्शन f(s,x) के लिए, और 1,...,b में प्रत्येक निर्देशांक j के लिए, f द्वारा निरूपित करें<sub>j</sub>(s,x) f का j-वां निर्देशांक। लानत होना<sub>j</sub>b+a वेरिएबल्स में एक पूर्णांक फ़ंक्शन के रूप में देखा जा सकता है। मान लीजिए कि ऐसा प्रत्येक एफ<sub>j</sub>गैर-ऋणात्मक गुणांक वाला एक बहुपद है। इसे s=(z) प्रतिस्थापित करके एकल चर z वाले बहुपद में परिवर्तित करें<sup>d1</sup>,...,z<sup>db</sup>) और x=(1,...,1). यदि z में परिणामी बहुपद की घात अधिकतम d है<sub>j</sub>, तो शर्त 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 के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है: यदि एस<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>, फिर: जी(एस<sub>1</sub>) ≤ आर<sup>जी</sup> · जी(एस<sub>2</sub>) (समस्याओं को न्यूनतम करने में); जी(एस<sub>1</sub>) ≥ आर<sup>(-G)</sup> · g(s<sub>2</sub>) (अधिकतमीकरण समस्याओं में)।
#मूल्य फलन द्वारा संवृत का संरक्षित रहना: एक पूर्णांक 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'') में बहुपद है।
#*सेट एस<sub>0</sub> प्रारंभिक अवस्थाओं की गणना एन और लॉग (एक्स) में समय बहुपद में की जा सकती है।
#*प्रारंभिक स्थितियों का समुच्चय ''S''<sub>0</sub> को ''n'' और log(''X'') में बहुपद समय में गणना की जा सकती है।
#*मान लीजिए वी<sub>j</sub>उन सभी मानों का समुच्चय बनें जो किसी स्थिति में निर्देशांक j में प्रकट हो सकते हैं। फिर, V में प्रत्येक मान का [[प्राकृतिक]] लघुगणक<sub>j</sub>अधिकतम एक बहुपद P है<sub>1</sub>(एन,लॉग(एक्स)).
#*''V<sub>j</sub>'' को स्थिति के निर्देशांक ''j'' में प्रकट होने वाले सभी मानों का समुच्चय कहें। तब, ''V<sub>j</sub>'' में प्रत्येक मान का [[प्राकृतिक|ln]] न केवल एक बहुपद P<sub>1</sub>(n,log(X)) में सबसे अधिक है।
#*यदि डी<sub>j</sub>=0, वी की कार्डिनैलिटी<sub>j</sub>अधिकतम एक बहुपद P है<sub>2</sub>(एन,लॉग(एक्स)).
#*यदि ''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>, जहां पी<sub>1</sub> स्थिति 3 से बहुपद है (प्रत्येक मान के एलएन पर एक ऊपरी सीमा जो एक राज्य वेक्टर में दिखाई दे सकती है)। ध्यान दें कि <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>, तो पी की परिभाषा के अनुसार<sub>1</sub>, प्रत्येक पूर्णांक जो राज्य-वेक्टर में दिखाई दे सकता है वह सीमा [0,r<sup>एल</sup>].
* <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,r<sup>एल</sup>] में एल+1 आर-अंतराल: <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>
* राज्य स्थान को आर-बॉक्स में विभाजित करें: प्रत्येक निर्देशांक k को डिग्री d के साथ<sub>k</sub>≥ 1 को उपरोक्त L+1 अंतराल में विभाजित किया गया है; प्रत्येक d के साथ समन्वय करता है<sub>k</sub>= 0 को P में विभाजित किया गया है<sub>2</sub>(n,log(X)) सिंगलटन अंतराल - निर्देशांक k के प्रत्येक संभावित मान के लिए एक अंतराल (जहाँ P<sub>2</sub> उपरोक्त शर्त 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-बॉक्स में हैं, तो वे (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>.
** ध्यान दें कि आर-बॉक्स की संख्या अधिकतम आर है। चूंकि बी एक निश्चित स्थिरांक है, यह आर इनपुट के आकार में बहुपद है और इसमें <math>1/\epsilon</math>.
** ध्यान दें कि ''r''-बॉक्स की संख्या अधिकतम ''R'' है। क्योंकि ''b'' एक निश्चित स्थिर संख्या है, इसलिए यह ''R'' इनपुट के आकार में बहुपद और <math>1/\epsilon</math> में है।


एफपीटीएएस डीपी के समान ही चलता है, लेकिन प्रत्येक चरण में, यह राज्य सेट को एक छोटे सेट टी में ट्रिम कर देता है<sub>k</sub>, जिसमें प्रत्येक आर-बॉक्स में बिल्कुल एक स्थिति होती है। FPTAS का एल्गोरिदम है:
एफपीटीएएस डीपी के समान ढंग से चलता है, लेकिन प्रत्येक चरण में, यह स्थिति समुच्चय को एक छोटे समुच्चय ''T<sub>k</sub>'' में काटता है, जो प्रत्येक r-बॉक्स में एक ही स्थिति को सम्मिलित करता है। एफपीटीएएस की एल्गोरिथम निम्नलिखित है:
* चलो टी<sub>0</sub> := एस<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय.
* मान लीजिए ''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>''}
एफपीटीएएस का रन-टाइम प्रत्येक टी में संभावित राज्यों की कुल संख्या में बहुपद है<sub>i</sub>, जो कि आर-बॉक्स की कुल संख्या है, जो कि अधिकतम आर है, जो एन, लॉग (एक्स) में बहुपद है, और <math>1/\epsilon</math>.
एफपीटीएएस का रनटाइम प्रत्येक ''T<sub>i</sub>'' में संभावित स्थितियों की कुल संख्या में बहुपद होता है, जो अधिकतम एकत्रित r-बॉक्स की कुल संख्या होती है, जो अधिकतम ''R'' होती है, जो बहुपद होती है ''n'', log(''X''), और <math>1/\epsilon</math> में।


ध्यान दें, प्रत्येक राज्य के लिए<sub>u</sub>यू में<sub>k</sub>, इसका उपसमुच्चय T<sub>k</sub>इसमें कम से कम एक राज्य शामिल है<sub>t</sub>वह (डी,आर)-एस के करीब है<sub>u</sub>. साथ ही, प्रत्येक यू<sub>k</sub>एस का एक उपसमुच्चय है<sub>k</sub>मूल (बिना छंटे हुए) डीपी में। एफपीटीएएस की शुद्धता साबित करने की मुख्य विधि है:<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}}  


0,...,n में प्रत्येक चरण k के लिए, प्रत्येक अवस्था s के लिए<sub>s</sub>एस में<sub>k</sub>, एक राज्य है s<sub>t</sub>टी में<sub>k</sub>वह है (डी,आर<sup>क</sup>)-स के करीब<sub>s</sub>. </ब्लॉककोट>
प्रत्येक चरण k में 0,...,n, प्रत्येक स्थिति ''s<sub>s</sub>'' ''S<sub>k</sub>'' में, एक ऐसी स्थिति ''s<sub>t</sub>'' होती है जो ''s<sub>s</sub>'' के (d,rk)-संवृत होती है।


इसका प्रमाण k पर प्रेरण द्वारा है। K=0 के लिए हमारे पास T है<sub>k</sub>=एस<sub>k</sub>; प्रत्येक अवस्था (d,1)-स्वयं के करीब है। मान लीजिए कि लेम्मा k-1 के लिए है। प्रत्येक राज्य के लिए एस<sub>s</sub>एस में<sub>k</sub>, चलो एस<sub>s-</sub>एस में इसके पूर्ववर्तियों में से एक बनें<sub>k-1</sub>, ताकि f(s<sub>s</sub><sub></sub>,x)=s<sub>s</sub>. प्रेरण धारणा के अनुसार, एक राज्य है<sub>t-</sub>टी में<sub>k-1</sub>, वह है (डी,आर<sup>k-1</sup>)-s के करीब<sub>s</sub><sub></sub>. चूंकि निकटता संक्रमणों द्वारा संरक्षित है (ऊपर शर्त 1), एफ(एस)।<sub>t</sub><sub>−</sub>,x) है (d,r<sup>k-1</sup>)-f(s) के करीब<sub>s</sub><sub>−</sub>,x)=s<sub>s</sub>. यह एफ(एस<sub>t</sub><sub></sub>,x) U में है<sub>k</sub>. ट्रिमिंग के बाद, एक राज्य है एस<sub>t</sub>टी में<sub>k</sub>वह (d,r)-f(s) के करीब है<sub>t-</sub>,एक्स)यह एस<sub>t</sub>है (डी,आर<sup></sup>)-स के करीब<sub>s</sub>.
इसका प्रमाण 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>'' के संवृत है।


अब राज्य पर विचार करें<sup>*</sup>एस में<sub>n</sub>, जो इष्टतम समाधान से मेल खाता है (अर्थात, g(s*)=OPT)। उपरोक्त लेम्मा के अनुसार, T में एक अवस्था t* है<sub>n</sub>, जो (डी,आर) है<sup>एन</sup>)-एस के करीब<sup>*</sup>. चूँकि निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है, g(t*) ≥ r<sup>(-Gn)</sup> · g(s*) अधिकतमीकरण समस्या के लिए। आर की परिभाषा के अनुसार, <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 बिन्स के योग को दर्शाता है। बी फ़ंक्शन हैं: प्रत्येक फ़ंक्शन जे अगले इनपुट को बिन जे में डालने का प्रतिनिधित्व करता है। फ़ंक्शन g(s) s का सबसे बड़ा तत्व चुनता है। एस<sub>0</sub> = {(0,...,0)}. चरम-परोपकार की शर्तें डिग्री-वेक्टर d=(1,...,1) और G=1 से संतुष्ट हैं। जब भी मशीनों की संख्या तय होती है तो परिणाम [[वर्दी-मशीन शेड्यूलिंग]] और असंबंधित-मशीन शेड्यूलिंग तक विस्तारित होता है (यह आवश्यक है क्योंकि आर - आर-बॉक्स की संख्या - बी में घातीय है)। निरूपित पीएम||<math>\max C_j</math> या Qm||<math>\max C_j</math> या आरएम||<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) = (s) के साथ<sub>1</sub>-एस<sub>2</sub>)<sup>2</sup>. अब, शर्त 2 का उल्लंघन हुआ है: राज्य (एस)।<sub>1</sub>,एस<sub>1</sub>) और (एस<sub>1</sub>,एस<sub>2</sub>) हो सकता है (डी,आर)-बंद, लेकिन जी(एस)।<sub>1</sub>,एस<sub>1</sub>) = 0 जबकि g(s<sub>1</sub>,एस<sub>2</sub>) > 0. इसलिए उपरोक्त प्रमेय लागू नहीं किया जा सकता है। दरअसल, समस्या में एफपीटीएएस नहीं है जब तक कि पी=एनपी न हो, क्योंकि एफपीटीएएस का उपयोग पॉलीटाइम में यह तय करने के लिए किया जा सकता है कि इष्टतम मान 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> द्वारा दर्शाया गया है।


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>


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


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


* फ़िल्टरिंग फ़ंक्शंस का एक सेट एच, एफ के समान कार्डिनैलिटी का। प्रत्येक फ़ंक्शन एच<sub>i</sub>H में एक जोड़ी (स्टेट, इनपुट) को बूलियन मान पर मैप किया जाता है। मान सत्य होना चाहिए यदि और केवल यदि संक्रमण f को सक्रिय किया जा रहा है<sub>i</sub>इस जोड़ी पर एक वैध स्थिति का नेतृत्व होगा।
* एक ''फ़िल्टरिंग फलनों'' का समुच्चय ''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>
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>


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 176: Line 170:
== बाहरी संबंध ==
== बाहरी संबंध ==


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


[[Category: Machine Translated Page]]
[[Category:CS1 errors]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:जटिलता वर्ग]]
[[Category:सन्निकटन एल्गोरिदम]]
[[Category:Vigyan Ready]]

Latest revision as of 07:19, 23 September 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.


बाहरी संबंध