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

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

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

महत्वपूर्ण बात यह है कि एक FPTAS का रनटाइम समस्या के आकार और 1/ε में पॉलिनोमियल होता है। यह एक सामान्य पॉलिनोमियल-समय आपकर्षण योजना (PTAS) के विपरीत है। एक सामान्य PTAS का रनटाइम हर विशिष्ट ε के लिए समस्या के आकार में पॉलिनोमियल होता है, लेकिन 1/ε में विश्वसनीयता के साथ विस्तारणशील हो सकता है।

FPTAS शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक FPTAS हो। FPTAS PTAS की एक उपसमूह है, और जब तक P = NP नहीं हो, यह एक सख्त उपसमूह है।

अन्य जटिलता वर्गों से संबंध

FPTAS में सभी समस्याएँ मानक पैरामीटरीकरण के संदर्भ में निश्चित पैरामीटर संवाद्य हैं।

किसी भी पॉलिनोमियल बाउंडेड उद्देश्य कार्य के साथ कोई भी मजबूत NP-कठिन अनुकुलन समस्या FPTAS नहीं हो सकता, जब तक P=NP नहीं हो। हालांकि, उलटी बात नहीं सिद्ध होती: उदाहरण स्वरूपन, यदि P NP से बराबर नहीं है, तो डोरा में दो प्रतिबंधों के साथ यह स्थिरता मजबूत NP-कठिन नहीं है, लेकिन जब तक आदर्श उद्देश्य पॉलिनोमियल बाउंडेड नहीं हो, तो उसका कोई FPTAS नहीं है।

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

वेगिंगर ने एक ऐसे विशेष श्रेणी के गतिशील प्रोग्रामिंग को एक FPTAS में बदलने के लिए एक सामान्य योजना प्रस्तुत की।

इनपुट

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

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

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

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

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

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

• चलो एस₀ := प्रारंभिक अवस्थाओं का समुच्चय.
• k = 1 से n के लिए करें:
  • चलो एस_k:= {f(s,x_k) | एफ में एफ, एस में एस_k−1}
• आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस_n}.

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

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

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

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

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)) में सबसे अधिक हो सकती है।

हर अत्यधिक दयालु समस्या के लिए, गतिशील कार्यक्रम को एक FPTAS में परिवर्तित किया जा सकता है। निर्धारित करें:

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

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

• मान लीजिए T0 := S0 = प्रारंभिक अवस्थाओं का समुच्चय।
• k = 1 से n के लिए करें:
  • चलो यू_k:= {f(s,x_k) | एफ में एफ, टी में एस_k−1}
  • मान लीजिए टी_k:= यू की एक छंटनी प्रति_k: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं_k, T में बिल्कुल एक अवस्था रखें_k.
• आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस_n}.

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

ध्यान दें कि प्रत्येक स्थिति su में Uk में, उसका उपसमूह Tk में कम से कम एक स्थिति st होता है जो su के (d, r)-नजदीक होता है। भी, प्रत्येक Uk प्रारंभिक (बिना काटे गए) DP के स्थिति सेट Sk की एक उपसेट है। FPTAS की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:

प्रत्येक कदम 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) के करीब होती है। यह सेंट (डी,आरके)-एसएस के करीब है।

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

उदाहरण

यहां अत्यंत-परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार FPTAS है।

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

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

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

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

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

5. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: एम||$\sum w_{j}|C_{j}|$।

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

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

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

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

• चलिए एस₀ := प्रारंभिक अवस्थाओं का समुच्चय.
• k = 1 से n के लिए करें:
  • चलो एस_k := {एफ_j(एस,एक्स_k) | एफ_jएफ में, एस में एस_k−1, एच_j(एस,एक्स_k)=सत्य' }, जहां h_jसंक्रमण फ़ंक्शन f के अनुरूप फ़िल्टर फ़ंक्शन है_j.
• आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस_n}.

किसी समस्या को 'परोपकारी' कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो उपरोक्त शर्तों 1, 2, 3 का विस्तार करती है):

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

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

• चलो टी₀ := एस₀ = प्रारंभिक अवस्थाओं का समुच्चय.
• k = 1 से n के लिए करें:
  • चलो यू_k := {एफ_j(एस,एक्स_k) | एफ_jएफ में, टी में एस_k−1, एच_j(एस,एक्स_k)=सत्य' }, जहां h_jसंक्रमण फ़ंक्शन f के अनुरूप फ़िल्टर फ़ंक्शन है_j.
  • मान लीजिए टी_k:= यू की एक छंटनी प्रति_k: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं_k, एक ऐसा तत्व चुनें जो यू में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता हो_k,' और इसे टी में डालें_k.
• आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस_n}.

उदाहरण

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

1. 0-1 बस्ता समस्या कल्याणकारी है। यहां, हमारे पास a=2 है: प्रत्येक इनपुट 2-वेक्टर (वजन, मान) है। बी=2 के साथ एक डीपी है: प्रत्येक राज्य एनकोड करता है (वर्तमान वजन, वर्तमान मूल्य)। दो संक्रमण कार्य हैं: एफ₁ अगला इनपुट आइटम जोड़ने से मेल खाता है, और एफ₂ इसे न जोड़ने से मेल खाता है। संबंधित फ़िल्टर फ़ंक्शन हैं: h₁ सत्यापित करता है कि अगले इनपुट आइटम का वजन अधिकतम नैपसेक क्षमता पर है; एच₂ हमेशा सत्य लौटाता है। मान फ़ंक्शन g(s) s लौटाता है₂. प्रारंभिक अवस्था-सेट {(0,0)} है। डिग्री वेक्टर (1,1) है। प्रभुत्व का रिश्ता तुच्छ है. अर्ध-प्रभुत्व संबंध केवल भार निर्देशांक की तुलना करता है: s अर्ध-प्रभुत्व t यदि s₁ ≤ टी₁. इसका निहितार्थ यह है कि, यदि राज्य t का भार राज्य s से अधिक है, तो संक्रमण कार्यों को t और s के बीच निकटता को संरक्षित नहीं करने की अनुमति है (उदाहरण के लिए, यह संभव है कि s का कोई उत्तराधिकारी हो और t के पास कोई संगत उत्तराधिकारी न हो)। इसी तरह का एल्गोरिदम पहले इबारा और किम द्वारा प्रस्तुत किया गया था। इस FPTAS के रन-टाइम को बेहतर बनाया जा सकता है $O(n\log {1/\epsilon }+1/\epsilon ^{4})$ पूर्णांकों पर संचालन. बाद में घातांक को सुधार कर 2.5 कर दिया गया।

• नोट: 2-भारित नैपसेक समस्या पर विचार करें, जहां प्रत्येक वस्तु के दो वजन और एक मूल्य होता है, और लक्ष्य मूल्य को अधिकतम करना है ताकि कुल वजन के वर्गों का योग अधिकतम नैपसेक क्षमता हो: $\left(\sum _{k\in K}w_{1,k}\right)^{2}+\left(\sum _{k\in K}w_{2,k}\right)^{2}\leq W$. हम इसे एक समान डीपी का उपयोग करके हल कर सकते हैं, जहां प्रत्येक स्थिति (वर्तमान वजन 1, वर्तमान वजन 2, मूल्य) है। अर्ध-प्रभुत्व संबंध को इस प्रकार संशोधित किया जाना चाहिए: s अर्ध-प्रभुत्व t iff (s)।₁²+s₂²) ≤ (t₁²+t₂²). लेकिन यह उपरोक्त शर्त 1 का उल्लंघन करता है: अर्ध-प्रभुत्व संक्रमण कार्यों द्वारा संरक्षित नहीं है [उदाहरण के लिए, राज्य (2,2,..) अर्ध-प्रभुत्व (1,3,..); लेकिन दोनों राज्यों में इनपुट (2,0,..) जोड़ने के बाद, परिणाम (4,2,..) अर्ध-प्रभुत्व (3,3,..)] नहीं होता है। अतः प्रमेय का प्रयोग नहीं किया जा सकता। वास्तव में, इस समस्या का कोई FPTAS नहीं है जब तक कि P=NP न हो। द्वि-आयामी नैपसेक समस्या के लिए भी यही सच है। एकाधिक उपसमुच्चय योग समस्या के लिए भी यही सच है: अर्ध-प्रभुत्व संबंध होना चाहिए: s अर्ध-प्रभुत्व t यदि अधिकतम_1,s₂) ≤ अधिकतम(t_1,t₂), लेकिन यह उपरोक्त उदाहरण के अनुसार, परिवर्तनों द्वारा संरक्षित नहीं है।

2. एक ही मशीन पर विलंबित कार्यों की भारित संख्या को कम करना, या प्रारंभिक कार्यों की भारित संख्या को अधिकतम करना; निरूपित 1||$\sum w_{j}U_{j}$.

3. विलंबित कार्यों की भारित संख्या को कम करने के लिए बैच शेड्यूलिंग: 1|बैच|$\sum w_{j}U_{j}$.

4. एक ही मशीन पर नौकरियों के बिगड़ने का कारण: 1|बिगड़ना|$\max C_{j}$.

5. एक मशीन पर कुल देर से काम: 1||$\sum V_{j}$.

6. एक मशीन पर कुल भारित विलंबित कार्य: 1||$\sum w_{j}V_{j}$.

गैर-उदाहरण

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

1. कुल विलंबता समस्या में 1||$\sum T_{j}$, लॉलर का गतिशील प्रोग्रामिंग सूत्रीकरण पुराने राज्य स्थान के सभी राज्यों को कुछ B बार अद्यतन करने की आवश्यकता है, जहाँ B, X (अधिकतम इनपुट आकार) के क्रम का है। आर्थिक लॉट-साइज़िंग के लिए डीपी के लिए भी यही सच है। इन मामलों में, एफ में संक्रमण कार्यों की संख्या बी है, जो लॉग (एक्स) में घातीय है, इसलिए दूसरी तकनीकी स्थिति का उल्लंघन होता है। स्टेट-ट्रिमिंग तकनीक उपयोगी नहीं है, लेकिन एक अन्य तकनीक - इनपुट-राउंडिंग - का उपयोग एफपीटीएएस को डिजाइन करने के लिए किया गया है। 2. विचरण न्यूनीकरण समस्या 1|| में$CTV$, वस्तुनिष्ठ कार्य है $g(s)=s_{5}-(s_{4}-s_{3})^{2}/n$, जो शर्त 2 का उल्लंघन करता है, इसलिए प्रमेय का उपयोग नहीं किया जा सकता है। लेकिन एफपीटीएएस को डिजाइन करने के लिए विभिन्न तकनीकों का उपयोग किया गया है।

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

• नैपसेक समस्या, साथ ही इसके कुछ प्रकार:
  • 0-1 बस्ता समस्या।
  • अनबाउंडेड नैपसेक समस्या।
  • डेल्टा-मॉड्यूलर बाधाओं के साथ बहुआयामी नैपसेक समस्या।
  • बहुउद्देश्यीय 0-1 बस्ता समस्या।
  • पैरामीट्रिक नैपसेक समस्या।
  • सममित द्विघात बस्ता समस्या।
• गणना-उपसमुच्चय-योग (#सबसेट योग समस्या) - अधिकतम सी के योग के साथ अलग-अलग उपसमुच्चय की संख्या ज्ञात करना।
• प्रतिबंधित सबसे छोटा पथ समस्या: विलंब बाधा के अधीन, ग्राफ़ में दो नोड्स के बीच न्यूनतम लागत वाला पथ ढूंढना।
• सबसे छोटे रास्ते और गैर-रैखिक उद्देश्य।
• किनारे का आवरण की गिनती|एज-कवर।
• वेक्टर उपसमुच्चय खोज समस्या जहां आयाम निश्चित है।

यह भी देखें

• परोपकारी गतिशील कार्यक्रम, जो एक एफपीटीएएस को स्वीकार करते हैं, एक विकासवादी एल्गोरिदम को भी स्वीकार करते हैं।

बाहरी संबंध

• Complexity Zoo: FPTAS