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

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

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

महत्वपूर्ण बात यह है कि एफपीटीएएस का रन-टाइम समस्या आकार और 1/ε में बहुपद है। यह सामान्य बहुपद-समय सन्निकटन योजना (पीटीएएस) के विपरीत है। सामान्य पीटीएएस का रन-टाइम प्रत्येक विशिष्ट ε के लिए समस्या आकार में बहुपद है, लेकिन 1/ε में घातीय हो सकता है। एफपीटीएएस शब्द का उपयोग एफपीटीएएस वाली समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। एफपीटीएएस पीटीएएस का एक उपसमुच्चय है, और जब तक पी = एनपी समस्या नहीं है|पी = एनपी, यह एक सख्त उपसमुच्चय है।

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

एफपीटीएएस में सभी समस्याएं मानक पैरामीटराइजेशन के संबंध में निश्चित-पैरामीटर ट्रैक करने योग्य हैं। बहुपद रूप से बंधे उद्देश्य फ़ंक्शन के साथ किसी भी दृढ़ता से एनपी-पूर्ण | दृढ़ता से एनपी-हार्ड अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि पी = एनपी न हो। हालाँकि, उलटा विफल रहता है: उदा. यदि पी, एनपी के बराबर नहीं है, तो नैपसैक समस्याओं की सूची#एकाधिक बाधाएं दृढ़ता से एनपी-हार्ड नहीं हैं, लेकिन इष्टतम उद्देश्य बहुपद रूप से बंधे होने पर भी कोई एफपीटीएएस नहीं है।

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

गेरहार्ड जे. वोएजिंजर गतिशील प्रोग्रामिंग के एक निश्चित वर्ग को एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की गई।

इनपुट

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

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

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

यह माना जाता है कि समस्या में राज्यों का उपयोग करते हुए एक गतिशील-प्रोग्रामिंग (डीपी) एल्गोरिदम है। प्रत्येक राज्य कुछ से बना एक वेक्टर है $b$ गैर-ऋणात्मक पूर्णांक, कहाँ $b$ इनपुट से स्वतंत्र है. डीपी n चरणों में काम करती है। प्रत्येक चरण i पर, यह इनपुट x को संसाधित करता है_i, और राज्यों एस का एक सेट बनाता है_i. प्रत्येक राज्य इनपुट x का उपयोग करके समस्या का आंशिक समाधान एन्कोड करता है₁,...,एक्स_i. डीपी के घटक हैं:

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

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

• चलो एस₀ := प्रारंभिक अवस्थाओं का समुच्चय.
• 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(लॉग X) में है।

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

इसे औपचारिक रूप देने के लिए, हम मानते हैं कि मौजूदा समस्या में एक गैर-नकारात्मक पूर्णांक वेक्टर d = (d) है₁,...,डी_b), जिसे समस्या का डिग्री वेक्टर कहा जाता है। प्रत्येक वास्तविक संख्या r>1 के लिए, हम कहते हैं कि दो राज्य-वेक्टर s हैं₁,एस₂ हैं (d,r)-बंद करें यदि, 1,...,b में प्रत्येक निर्देशांक j के लिए: $r^{-d_{j}}\cdot s_{1,j}\leq s_{2,j}\leq r^{d_{j}}\cdot s_{1,j}$ (विशेष रूप से, यदि डी_j=0 कुछ j के लिए, तो $s_{1,j}=s_{2,j}$).

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

1. निकटता को संक्रमण कार्यों द्वारा संरक्षित किया जाता है: किसी भी r>1 के लिए, किसी भी संक्रमण फ़ंक्शन f के लिए F में, किसी भी इनपुट-वेक्टर x के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए₁,एस₂, निम्नलिखित धारण करता है: यदि एस₁ (डी,आर)-एस के करीब है₂, फिर f(s₁,x) (d,r)-f(s) के करीब है₂,एक्स)।
   • इसके लिए पर्याप्त शर्त की जाँच निम्नानुसार की जा सकती है। F में प्रत्येक फ़ंक्शन f(s,x) के लिए, और 1,...,b में प्रत्येक निर्देशांक j के लिए, f द्वारा निरूपित करें_j(s,x) f का j-वां निर्देशांक। लानत होना_jb+a वेरिएबल्स में एक पूर्णांक फ़ंक्शन के रूप में देखा जा सकता है। मान लीजिए कि ऐसा प्रत्येक एफ_jगैर-ऋणात्मक गुणांक वाला एक बहुपद है। इसे s=(z) प्रतिस्थापित करके एकल चर z वाले बहुपद में परिवर्तित करें^d1,...,z^db) और x=(1,...,1). यदि z में परिणामी बहुपद की घात अधिकतम d है_j, तो शर्त 1 संतुष्ट है।
2. निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है: एक पूर्णांक G ≥ 0 मौजूद है (जो मान फ़ंक्शन g और डिग्री वेक्टर d का एक फ़ंक्शन है), जैसे कि किसी भी r>1 के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए₁,एस₂, निम्नलिखित धारण करता है: यदि एस₁ (डी,आर)-एस के करीब है₂, फिर: जी(एस₁) ≤ आर^जी · जी(एस₂) (समस्याओं को न्यूनतम करने में); जी(एस₁) ≥ आर^(-G) · g(s₂) (अधिकतमीकरण समस्याओं में)।
   • इसके लिए एक पर्याप्त शर्त यह है कि फ़ंक्शन g गैर-नकारात्मक गुणांक वाला एक बहुपद फ़ंक्शन (b चर का) है।
3. तकनीकी शर्तें:
   • F में सभी संक्रमण फ़ंक्शन f और मान फ़ंक्शन g का मूल्यांकन पॉलीटाइम में किया जा सकता है।
   • संख्या |F| संक्रमण फलनों का n और log(X) में बहुपद है।
   • सेट एस₀ प्रारंभिक अवस्थाओं की गणना एन और लॉग (एक्स) में समय बहुपद में की जा सकती है।
   • मान लीजिए वी_jउन सभी मानों का समुच्चय बनें जो किसी स्थिति में निर्देशांक j में प्रकट हो सकते हैं। फिर, V में प्रत्येक मान का प्राकृतिक लघुगणक_jअधिकतम एक बहुपद P है₁(एन,लॉग(एक्स)).
   • यदि डी_j=0, वी की कार्डिनैलिटी_jअधिकतम एक बहुपद P है₂(एन,लॉग(एक्स)).

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

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

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

एफपीटीएएस का रन-टाइम प्रत्येक टी में संभावित राज्यों की कुल संख्या में बहुपद है_i, जो कि आर-बॉक्स की कुल संख्या है, जो कि अधिकतम आर है, जो एन, लॉग (एक्स) में बहुपद है, और $1/\epsilon$.

ध्यान दें, प्रत्येक राज्य के लिए_uयू में_k, इसका उपसमुच्चय T_kइसमें कम से कम एक राज्य शामिल है_tवह (डी,आर)-एस के करीब है_u. साथ ही, प्रत्येक यू_kएस का एक उपसमुच्चय है_kमूल (बिना छंटे हुए) डीपी में। एफपीटीएएस की शुद्धता साबित करने की मुख्य विधि है: <ब्लॉककोट>

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

इसका प्रमाण k पर प्रेरण द्वारा है। K=0 के लिए हमारे पास T है_k=एस_k; प्रत्येक अवस्था (d,1)-स्वयं के करीब है। मान लीजिए कि लेम्मा k-1 के लिए है। प्रत्येक राज्य के लिए एस_sएस में_k, चलो एस_s-एस में इसके पूर्ववर्तियों में से एक बनें_k-1, ताकि f(s_s−,x)=s_s. प्रेरण धारणा के अनुसार, एक राज्य है_t-टी में_k-1, वह है (डी,आर^k-1)-s के करीब_s−. चूंकि निकटता संक्रमणों द्वारा संरक्षित है (ऊपर शर्त 1), एफ(एस)।_t−,x) है (d,r^k-1)-f(s) के करीब_s−,x)=s_s. यह एफ(एस_t−,x) U में है_k. ट्रिमिंग के बाद, एक राज्य है एस_tटी में_kवह (d,r)-f(s) के करीब है_t-,एक्स)। यह एस_tहै (डी,आर^क)-स के करीब_s.

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

उदाहरण

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

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

• नोट: विशेष मामले b=2 पर विचार करें, जहां लक्ष्य दो भागों के योग के बीच अंतर के वर्ग को कम करना है। उसी DP का उपयोग किया जा सकता है, लेकिन इस बार मान फ़ंक्शन g(s) = (s) के साथ₁-एस₂)². अब, शर्त 2 का उल्लंघन हुआ है: राज्य (एस)।₁,एस₁) और (एस₁,एस₂) हो सकता है (डी,आर)-बंद, लेकिन जी(एस)।₁,एस₁) = 0 जबकि g(s₁,एस₂) > 0. इसलिए उपरोक्त प्रमेय लागू नहीं किया जा सकता है। दरअसल, समस्या में एफपीटीएएस नहीं है जब तक कि पी=एनपी न हो, क्योंकि एफपीटीएएस का उपयोग पॉलीटाइम में यह तय करने के लिए किया जा सकता है कि इष्टतम मान 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}|$.

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

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

• फ़िल्टरिंग फ़ंक्शंस का एक सेट एच, एफ के समान कार्डिनैलिटी का। प्रत्येक फ़ंक्शन एच_iH में एक जोड़ी (स्टेट, इनपुट) को बूलियन मान पर मैप किया जाता है। मान सत्य होना चाहिए यदि और केवल यदि संक्रमण f को सक्रिय किया जा रहा है_iइस जोड़ी पर एक वैध स्थिति का नेतृत्व होगा।
• एक प्रभुत्व संबंध, जो राज्यों पर एक आंशिक आदेश है (कोई उदासीनता नहीं, सभी जोड़े तुलनीय नहीं हैं), और एक अर्ध-प्रभुत्व संबंध जो राज्यों पर एक कुल पूर्व आदेश है (उदासीनता की अनुमति है, सभी जोड़े तुलनीय हैं)।

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

• चलिए एस₀ := प्रारंभिक अवस्थाओं का समुच्चय.
• 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