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

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

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

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

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

अन्य कम्प्लेक्सिटी वर्गों से संबंध

एफपीटीएएस में सभी समस्याएं मानक पैरामीटरीकरण के संबंध में निश्चित-पैरामीटर पर आधारित हैं।

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

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

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

इनपुट

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

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

अत्यंत सरल डायनामिक प्रोग्राम

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

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

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

• मान लीजिए S₀ := प्रारंभिक अवस्थाओं का समुच्चय।
• k = 1 से n के लिए करें:
  • समुच्चय S_k := {f(s,x_k) | f in F, s in S_k−1}
• आउटपुट न्यूनतम/अधिकतम {g(s) | s in S_n}।

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

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

इसे औपचारिकत: इसे हम मानते हैं कि समस्या के पास एक गैर-नकारात्मक पूर्णांक सदिश d = (d₁,...,d_b) है, जिसे समस्या का डिग्री सदिश कहा जाता है। प्रत्येक वास्तविक संख्या r>1 के लिए, हम कहते हैं कि दो स्थिति-सदिश s₁,s₂ (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 के लिए d_j=0 है, तो $s_{1,j}=s_{2,j}$)।

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

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

प्रत्येक अत्यधिक बेनिवॉलेंट समस्या के लिए, डायनामिक कार्यक्रम को एक एफपीटीएएस में परिवर्तित किया जा सकता है। निर्धारित करें:

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

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

• मान लीजिए T₀  := S₀ = प्रारंभिक अवस्थाओं का समुच्चय।
• k = 1 से n के लिए करें:
  • मान लीजिए U_k := {f(s,x_k) | f in F, s in T_k−1}
  • मान लीजिए T_k := U_k की एक संक्षिप्त प्रति: प्रत्येक r-बॉक्स के लिए जिसमें U_k के एक या अधिक राज्य हैं, T_k में ठीक एक स्थिति रखें।
• आउटपुट न्यूनतम/अधिकतम {g(s) | s in T_n}।

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

ध्यान दें कि प्रत्येक स्थिति s_u में U_k में, उसका उपसमुच्चय T_k में कम से कम एक स्थिति s_t होता है जो su के (d, r)-संवृत होता है। भी, प्रत्येक U_k प्रारंभिक (बिना काटे गए) डीपी के स्थिति समुच्चय S_k की एक उपसमुच्चय है। एफपीटीएएस की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:

प्रत्येक चरण k में 0,...,n, प्रत्येक स्थिति s_s S_k में, एक ऐसी स्थिति s_t होती है जो s_s के (d,rk)-संवृत होती है।

इसका प्रमाण k पर प्रेरण द्वारा है। k=0 के लिए हमारे पास T_k=S_k है; प्रत्येक अवस्था (d,1)-स्वयं के संवृत है। मान लीजिए कि लेम्मा k-1 के लिए धारण करता है। S_k में प्रत्येक अवस्था s_s के लिए, s_s- को S_k-1 में अपने पूर्ववर्तियों में से एक होने दें, ताकि f(s_s−,x)=s_s। प्रेरण धारणा के अनुसार, T_k-1 में एक अवस्था s_t - है, अर्थात (d,rk-1)-s_s− के संवृत। चूंकि संवृत संक्रमणों (उपरोक्त शर्त 1) द्वारा संरक्षित है, f(s_t−,x) (d,rk-1)-f(s_s−,x)=s_s के संवृत है। यह f(s_t−,x) यूके में है। ट्रिमिंग के बाद, T_k में एक अवस्था s_t होती है जो कि (d,r)-f(s_t-,x) के संवृत होती है। यह सेंट (d,r^k)-s_s के संवृत है।

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

उदाहरण

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

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

• ध्यान दें: एक विशेष प्रकार की स्थिति b=2 को विचार करें, जहाँ लक्ष्य दो भागों के योग के बीच अंतर के वर्ग को कम करना है। एक ही डीपी का उपयोग किया जा सकता है, लेकिन इस बार मूल्य फलन g(s) = (s₁-s₂)² के साथ, जहाँ s₁ और s₂ दो भागों के योग होते हैं। अब, शर्त 2 का उल्लंघन होता है: स्थितियाँ (s₁,s₁) और (s₁,s₂) (d,r)-संवृत हो सकती हैं, लेकिन g(s₁,s₁) = 0 होता है जबकि g(s₁,s₂) > 0 होता है। इस प्रकार, उपरोक्त सिद्धांत का लागू नहीं हो सकता है। यद्यपि, समस्या के पास एफपीटीएएस नहीं होता है जब तक P=NP नहीं होता है, क्योंकि एफपीटीएएस का पॉलिटाइम में उपयोग करके निर्णय किया जा सकता है कि श्रेष्ठ मूल्य 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. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: m||$\sum w_{j}|C_{j}|$।

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

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

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

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

• मान लीजिए S₀ := प्रारंभिक अवस्थाओं का समुच्चय।
• k = 1 से n के लिए करें:
  • मान लीजिए S_k := {f_j(s,x_k) | f_j in F, s in S_k−1, h_j(s,x_k)=True }, जहां h_j ट्रांज़िशन फलन f_j के अनुरूप फ़िल्टर फलन है।
• आउटपुट का न्यूनतम/अधिकतम {g(s) | s in S_n}।

एक समस्या को बेनिवॉलेंट कहा जाता है यदि वह निम्नलिखित शर्तों को पूरा करती है (जो ऊपर दी गई शर्तों 1, 2, 3 को विस्तारित करती हैं):

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

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

• मान लीजिए T₀ := S₀ = प्रारंभिक अवस्थाओं का समुच्चय।
• k = 1 से n के लिए करें:
  • मान लीजिए U_k := {f_j(s,x_k) | f_j in F, s in T_k−1, h_j(s,x_k)=True }, जहां h_j संक्रमण फलन f_j के अनुरूप फ़िल्टर फलन है।
  • मान लीजिए T_k := U_k की एक छंटनी की गई प्रति: प्रत्येक r-बॉक्स के लिए जिसमें U_k के एक या अधिक स्थिति सम्मिलित हैं, एक एकल तत्व चुनें जो U_k में अन्य सभी तत्वों पर अर्ध-प्रभुत्व रखता है, और इसे T_k में डालें।
• आउटपुट का न्यूनतम/अधिकतम {g(s) | s in T_n}।

उदाहरण

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

1. 0-1 नैपसैक समस्या बेनिवॉलेंट है। यहाँ, a=2 है: प्रत्येक इनपुट एक 2-सदिश (वेट, मूल्य) होता है। हमारे पास b=2 है: प्रत्येक स्थिति (वर्तमान वेट, वर्तमान मूल्य) को कोड करती है। दो परियोजना फलन होते हैं: f₁ अगले इनपुट आइटम को जोड़ने का संदर्भ देता है, और f₂ उसे नहीं जोड़ने का। उसके संबंधित फ़िल्टर फलन हैं: h₁ यह सत्यापित करता है कि अगले इनपुट आइटम का वेट किन्नर क्षमता से कम है; h2 हमेशा सच की वापसी करता है। मूल्य फलन g(s) s₂ को वापसी करता है। प्रारंभिक स्थिति-समुच्चय है {(0,0)}। डिग्री सदिश (1,1) है। डॉमिनेट संबंध घटित है। क्वासी-डॉमिनेटता संबंध केवल वेट समन्वय करता है: s ने तीव्रीक संबंध है तब t का वेट t₁ से कम या बराबर होता है। इसका अर्थ है कि, यदि स्थिति t का स्थिति s से अधिक वेट है, तो परियोजना फलनों को तकनीकी रूप से t और s के बीच समर्पण को संरक्षित नहीं करने की अनुमति है (यह संभव है, उदाहरणार्थ, कि s के एक सफलता कारक है और t का उसके समर्पक का उपयुक्त सफलता कारक नहीं है)। एक समान एल्गोरिथ्म पहले Ibarra और Kim ने प्रस्तुत किया था। इस एफपीटीएएस की रनटाइम को $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,..) को क्वासी-डॉमिनेटता नहीं करता है। इसलिए यह सिद्धांत का उपयोग नहीं किया जा सकता है। वास्तव में, यह समस्या एफपीटीएएस नहीं है जब तक P=NP नहीं हो। ऐसा ही दो-विमीय नैपसैक समस्या के लिए भी है। ऐसा ही एकाधिक उपसमुच्चय समस्या के लिए भी है: क्वासी-डॉमिनेटता संबंध इस तरह होना चाहिए: s तीव्रीक तो t iff max(s_1,s₂) ≤ max(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 (अधिकतम इनपुट आकार) के आदर्श में होता है। यही समान ब्यवहार आर्थिक लॉट-साइजिंग के लिए डीपी के लिए भी होता है। इन स्थितियों में, F में परियोजना फलनों की संख्या B होती है, जो लॉग(X) में अपेक्षित होती है, इसलिए दूसरी तकनीकी शर्त का उल्लंघन हो जाता है। स्थिति-काटन तकनीक उपयोगी नहीं होती है, लेकिन एक दूसरी तकनीक - इनपुट-राउंडिंग - का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।

2. वैरिएंस मिनिमाइजेशन समस्या 1||$CTV$ में, उद्देश्य फलन $g(s)=s_{5}-(s_{4}-s_{3})^{2}/n$ है, जो शर्त 2 का उल्लंघन करता है, इसलिए सिद्धांत का उपयोग नहीं किया जा सकता है। लेकिन विभिन्न तकनीकों का उपयोग एक एफपीटीएएस का डिज़ाइन करने के लिए किया गया है।

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

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

यह भी देखें

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

बाहरी संबंध

• Complexity Zoo: एफपीटीएएस