View source for पूर्ण बहुपद-काल सन्निकटन प्रणाली

पूर्ण बहुपद-समय सन्निकटन योजना (एफपीटीएएस) फ़ंक्शन समस्याओं, विशेष रूप से [[अनुकूलन समस्या]]ओं के अनुमानित समाधान खोजने के लिए एक [[कलन विधि]] है। एक FPTAS इनपुट के रूप में समस्या का एक उदाहरण और एक पैरामीटर ε > 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>
एफपीटीएएस शब्द का उपयोग एफपीटीएएस वाली समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। एफपीटीएएस पीटीएएस का एक उपसमुच्चय है, और जब तक पी = एनपी समस्या नहीं है|पी = एनपी, यह एक सख्त उपसमुच्चय है।<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>
बहुपद रूप से बंधे उद्देश्य फ़ंक्शन के साथ किसी भी [[दृढ़ता से एनपी-पूर्ण]] | दृढ़ता से एनपी-हार्ड अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि पी = एनपी न हो।<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> [[गतिशील प्रोग्रामिंग]] के एक निश्चित वर्ग को एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की गई।

=== इनपुट ===
यह योजना अनुकूलन समस्याओं को संभालती है जिसमें इनपुट को निम्नानुसार परिभाषित किया गया है:
*इनपुट n वैक्टर, x से बना है<sub>1</sub>,...,एक्स<sub>n</sub>.
* प्रत्येक इनपुट वेक्टर कुछ से बना होता है <math>a</math> गैर-ऋणात्मक पूर्णांक, कहाँ <math>a</math> इनपुट पर निर्भर हो सकता है.
* इनपुट वैक्टर के सभी घटक बाइनरी में एन्कोड किए गए हैं। तो समस्या का आकार 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>. डीपी के घटक हैं:

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

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

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

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

# ''निकटता को संक्रमण कार्यों द्वारा संरक्षित किया जाता है'': किसी भी ''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>,एक्स)।
#*इसके लिए पर्याप्त शर्त की जाँच निम्नानुसार की जा सकती है। 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 संतुष्ट है।
#निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है: एक पूर्णांक 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 गैर-नकारात्मक गुणांक वाला एक बहुपद फ़ंक्शन (b चर का) है।
#तकनीकी शर्तें:
#*F में सभी संक्रमण फ़ंक्शन f और मान फ़ंक्शन g का मूल्यांकन पॉलीटाइम में किया जा सकता है।
#*संख्या |F| संक्रमण फलनों का n और log(X) में बहुपद है।
#*सेट एस<sub>0</sub> प्रारंभिक अवस्थाओं की गणना एन और लॉग (एक्स) में समय बहुपद में की जा सकती है।
#*मान लीजिए वी<sub>j</sub>उन सभी मानों का समुच्चय बनें जो किसी स्थिति में निर्देशांक j में प्रकट हो सकते हैं। फिर, V में प्रत्येक मान का [[प्राकृतिक]] लघुगणक<sub>j</sub>अधिकतम एक बहुपद P है<sub>1</sub>(एन,लॉग(एक्स)).
#*यदि डी<sub>j</sub>=0, वी की कार्डिनैलिटी<sub>j</sub>अधिकतम एक बहुपद P है<sub>2</sub>(एन,लॉग(एक्स)).
प्रत्येक अत्यंत-परोपकारी समस्या के लिए, गतिशील कार्यक्रम को FPTAS में परिवर्तित किया जा सकता है। परिभाषित करना:

* <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>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>].
* सीमा को विभाजित करें [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>.
* राज्य स्थान को आर-बॉक्स में विभाजित करें: प्रत्येक निर्देशांक 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-बॉक्स में हैं, तो वे (d,r)-बंद हैं।
*<math>R := (L + 1 + P_2(n,\log{X}))^b</math>.
** ध्यान दें कि आर-बॉक्स की संख्या अधिकतम आर है। चूंकि बी एक निश्चित स्थिरांक है, यह आर इनपुट के आकार में बहुपद है और इसमें <math>1/\epsilon</math>.

एफपीटीएएस डीपी के समान ही चलता है, लेकिन प्रत्येक चरण में, यह राज्य सेट को एक छोटे सेट टी में ट्रिम कर देता है<sub>k</sub>, जिसमें प्रत्येक आर-बॉक्स में बिल्कुल एक स्थिति होती है। FPTAS का एल्गोरिदम है:
* चलो टी<sub>0</sub> := एस<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय.
* k = 1 से n के लिए करें:
** चलो यू<sub>k</sub>:= {f(s,x<sub>k</sub>) | एफ में एफ, टी में एस<sub>k</sub><sub>−1</sub>}
**मान लीजिए टी<sub>k</sub>:= यू की एक छंटनी प्रति<sub>k</sub>: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं<sub>k</sub>, T में बिल्कुल एक अवस्था रखें<sub>k</sub>.
* आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस<sub>n</sub>}.
एफपीटीएएस का रन-टाइम प्रत्येक टी में संभावित राज्यों की कुल संख्या में बहुपद है<sub>i</sub>, जो कि आर-बॉक्स की कुल संख्या है, जो कि अधिकतम आर है, जो एन, लॉग (एक्स) में बहुपद है, और <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}} <ब्लॉककोट>

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

इसका प्रमाण 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>.

अब राज्य पर विचार करें<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>. एक समान तर्क न्यूनतमकरण समस्या के लिए काम करता है।

==== उदाहरण ====
यहां अत्यंत-परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार FPTAS है।<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>.

* नोट: विशेष मामले 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 है या नहीं।

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>.

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

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

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

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

* फ़िल्टरिंग फ़ंक्शंस का एक सेट एच, एफ के समान कार्डिनैलिटी का। प्रत्येक फ़ंक्शन एच<sub>i</sub>H में एक जोड़ी (स्टेट, इनपुट) को बूलियन मान पर मैप किया जाता है। मान सत्य होना चाहिए यदि और केवल यदि संक्रमण f को सक्रिय किया जा रहा है<sub>i</sub>इस जोड़ी पर एक वैध स्थिति का नेतृत्व होगा।
*एक प्रभुत्व संबंध, जो राज्यों पर एक [[आंशिक आदेश]] है (कोई उदासीनता नहीं, सभी जोड़े तुलनीय नहीं हैं), और एक अर्ध-प्रभुत्व संबंध जो राज्यों पर एक कुल पूर्व आदेश है (उदासीनता की अनुमति है, सभी जोड़े तुलनीय हैं)।
मूल डीपी को इस प्रकार संशोधित किया गया है:
*चलिए एस<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय.
* 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>.
* आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस<sub>n</sub>}.
किसी समस्या को 'परोपकारी' कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो उपरोक्त शर्तों 1, 2, 3 का विस्तार करती है):

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

प्रत्येक परोपकारी समस्या के लिए, गतिशील प्रोग्राम को दो बदलावों (बोल्डफेस्ड) के साथ उपरोक्त के समान एफपीटीएएस में परिवर्तित किया जा सकता है:
* चलो टी<sub>0</sub> := एस<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय.
* 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>.
**मान लीजिए टी<sub>k</sub>:= यू की एक छंटनी प्रति<sub>k</sub>: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं<sub>k</sub>, एक ऐसा तत्व चुनें जो यू में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता हो<sub>k</sub>,' और इसे टी में डालें<sub>k</sub>.
* आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस<sub>n</sub>}.

==== उदाहरण ====
यहां परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार एफपीटीएएस है।<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>
* नोट: 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. एक ही मशीन पर विलंबित कार्यों की भारित संख्या को कम करना, या प्रारंभिक कार्यों की भारित संख्या को अधिकतम करना; निरूपित 1||<math>\sum w_j U_j</math>.

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

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

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

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

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

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


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

*नैपसेक समस्या,<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>
**अनबाउंडेड नैपसेक समस्या।<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>
**बहुउद्देश्यीय 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|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 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>{{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=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}}


== बाहरी संबंध ==

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



[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]