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

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

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

महत्वपूर्ण यह है कि एफपीटीएएस के रनटाइम समस्या के आकार और 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>

एफपीटीएएस शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक एफपीटीएएस हो। एफपीटीएएस पीटीएएस की एक उपसमुच्चय है, और जब तक 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 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>,...,''x<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>'' को प्रोसेस करता है और स्थितियों का एक समुच्चय ''S<sub>i</sub>'' बनाता है। प्रत्येक स्थिति एक अधिंश समस्या को एनकोड करती है, ''x''<sub>1</sub>,...,''x<sub>i</sub>'' का उपयोग करके। डीपी के घटक हैं:

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

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

* मान लीजिए ''S''<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय।
* k = 1 से n के लिए करें:
** समुच्चय ''S<sub>k</sub>'' := {''f''(''s'',''x<sub>k</sub>'') | ''f'' in ''F'', ''s'' in ''S<sub>k</sub>''<sub>−1</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(log ''X'') में होता है।

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

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

* <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>, जहाँ 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>L</sup>''] को ''L''+1 ''r''-अंतरालों में विभाजित करें: <math>I_0 = [0]; I_1 = [1,r); I_2 = [r,r^2); \ldots ; I_L = [r^{L-1}, r^L]</math>।
* स्थिति समष्टि को ''r''-बॉक्स में विभाजित करें: प्रत्येक निर्देशिका ''k'' जिसका डिग्री ''d<sub>k</sub>'' ≥ 1 है, विशीर्णता ऊपर ''L''+1 अंतरालों में विभाजित किया जाता है; प्रत्येक निर्देशिका जिसका ''d<sub>k</sub>'' = 0 है, P<sub>2</sub>(n,log(X)) एकल अंतरालों में विभाजित किया जाता है - प्रत्येक संभावित मूल्य के लिए एक अंतराल (जहां P<sub>2</sub> उपरोक्त शर्त 3 से बहुपद है)।
**ध्यान दें कि प्रत्येक संभावित स्थिति केवल ''r''-बॉक्स में सम्मिलित है; यदि दो स्थितियाँ एक ही r-बॉक्स में हैं, तो वे ''(d,r)''-संवृत हैं।
*<math>R := (L + 1 + P_2(n,\log{X}))^b</math>.
** ध्यान दें कि ''r''-बॉक्स की संख्या अधिकतम ''R'' है। क्योंकि ''b'' एक निश्चित स्थिर संख्या है, इसलिए यह ''R'' इनपुट के आकार में बहुपद और <math>1/\epsilon</math> में है।

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

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

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

अब विचार करें कि स्थिति ''s''*, ''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> होता है। एक समान तर्क एक न्यूनीकरण समस्या के लिए काम करता है।

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

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 को विचार करें, जहाँ लक्ष्य दो भागों के योग के ''बीच अंतर के वर्ग'' को कम करना है। एक ही डीपी का उपयोग किया जा सकता है, लेकिन इस बार मूल्य फलन ''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) के साथ पूर्व-बेनिवॉलेंट है। इसे पूर्ण होने के समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।

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

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

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

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

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

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

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

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

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

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,..) को क्वासी-डॉमिनेटता नहीं करता है। इसलिए यह सिद्धांत का उपयोग नहीं किया जा सकता है। वास्तव में, यह समस्या एफपीटीएएस नहीं है जब तक 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>।

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> इन स्थितियों में, ''F'' में परियोजना फलनों की संख्या ''B'' होती है, जो लॉग(X) में अपेक्षित होती है, इसलिए दूसरी तकनीकी शर्त का उल्लंघन हो जाता है। स्थिति-काटन तकनीक उपयोगी नहीं होती है, लेकिन एक दूसरी तकनीक - इनपुट-राउंडिंग - का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।<ref>{{Cite journal|last=Lawler|first=E. L.|date=1982-12-01|title=संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना|url=https://dx.doi.org/10.1016/0167-6377%2882%2990022-0|journal=Operations Research Letters|language=en|volume=1|issue=6|pages=207–208|doi=10.1016/0167-6377(82)90022-0|issn=0167-6377}}</ref><ref>{{Cite journal|last1=van Hoesel|first1=C. P. M.|last2=Wagelmans|first2=Albert|date=1997-01-01|title=एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं|url=https://repub.eur.nl/pub/1406/|language=en}}</ref>

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

== कुछ अन्य समस्याएं जिनमें एफपीटीएएस है ==
*नैपसेक समस्या,<ref>{{Cite book|last=Vazirani|first=Vijay|url=https://archive.org/details/approximationalg00vazi_328|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2001|isbn=3540653678|location=Berlin|pages=[https://archive.org/details/approximationalg00vazi_328/page/n69 69]–70|oclc=47097680|url-access=limited}}</ref><ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|date=2004-03-01|title=नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग|url=https://doi.org/10.1023/B:JOCO.0000021934.29833.6b|journal=Journal of Combinatorial Optimization|language=en|volume=8|issue=1|pages=5–11|doi=10.1023/B:JOCO.0000021934.29833.6b|s2cid=36474745|issn=1573-2886}}</ref> साथ ही इसके कुछ प्रकार:
**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 एफपीटीएएस]

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