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

Revision as of 19:34, 14 August 2023

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

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

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

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

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

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

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

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

वेगिंगर^[6] ने एक ऐसे विशेष श्रेणी के गतिशील प्रोग्रामिंग को एक 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₋₁}
आउटपुट न्यूनतम/अधिकतम {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}$ )।

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

निकटता संक्रिया-समारोह द्वारा संरक्षित है: किसी भी 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 पूरी होती है।
मूल्य समारोह द्वारा निकटता का संरक्षित रहना: एक पूर्णांक 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 चरणों की) हो, जिसमें गैर-नकारात्मक संख्यात्मक हों।
तकनीकी शर्तें:
- सभी संक्रमण समारोह 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:=(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₋₁}
- मान लीजिए टी_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 की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:^[6]^: Lem.3.3

प्रत्येक कदम 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 है।^[6]

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₋₁, एच_j(एस,एक्स_k)=सत्य' }, जहां h_jसंक्रमण फ़ंक्शन f के अनुरूप फ़िल्टर फ़ंक्शन है_j.
आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस_n}.

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

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

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

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

उदाहरण

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

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

नोट: 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}$ , लॉलर का गतिशील प्रोग्रामिंग सूत्रीकरण^[10] पुराने राज्य स्थान के सभी राज्यों को कुछ B बार अद्यतन करने की आवश्यकता है, जहाँ B, X (अधिकतम इनपुट आकार) के क्रम का है। आर्थिक लॉट-साइज़िंग के लिए डीपी के लिए भी यही सच है।^[11] इन मामलों में, एफ में संक्रमण कार्यों की संख्या बी है, जो लॉग (एक्स) में घातीय है, इसलिए दूसरी तकनीकी स्थिति का उल्लंघन होता है। स्टेट-ट्रिमिंग तकनीक उपयोगी नहीं है, लेकिन एक अन्य तकनीक - इनपुट-राउंडिंग - का उपयोग एफपीटीएएस को डिजाइन करने के लिए किया गया है।^[12]^[13] 2. विचरण न्यूनीकरण समस्या 1|| में $CTV$ , वस्तुनिष्ठ कार्य है $g(s)=s_{5}-(s_{4}-s_{3})^{2}/n$ , जो शर्त 2 का उल्लंघन करता है, इसलिए प्रमेय का उपयोग नहीं किया जा सकता है। लेकिन एफपीटीएएस को डिजाइन करने के लिए विभिन्न तकनीकों का उपयोग किया गया है।^[14]^[15]

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

नैपसेक समस्या,^[16]^[17] साथ ही इसके कुछ प्रकार:
- 0-1 बस्ता समस्या।^[18]
- अनबाउंडेड नैपसेक समस्या।^[19]
- डेल्टा-मॉड्यूलर बाधाओं के साथ बहुआयामी नैपसेक समस्या।^[20]
- बहुउद्देश्यीय 0-1 बस्ता समस्या।^[21]
- पैरामीट्रिक नैपसेक समस्या।^[22]
- सममित द्विघात बस्ता समस्या।^[23]
गणना-उपसमुच्चय-योग (#सबसेट योग समस्या) - अधिकतम सी के योग के साथ अलग-अलग उपसमुच्चय की संख्या ज्ञात करना।^[24]
प्रतिबंधित सबसे छोटा पथ समस्या: विलंब बाधा के अधीन, ग्राफ़ में दो नोड्स के बीच न्यूनतम लागत वाला पथ ढूंढना।^[25]
सबसे छोटे रास्ते और गैर-रैखिक उद्देश्य।^[26]
किनारे का आवरण की गिनती|एज-कवर।^[27]
वेक्टर उपसमुच्चय खोज समस्या जहां आयाम निश्चित है।^[28]

यह भी देखें

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

संदर्भ

↑ 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.
↑ Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. See discussion following Definition 1.30 on p. 20.
↑ Cai, Liming; Chen, Jianer (June 1997). "फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर". Journal of Computer and System Sciences (in English). 54 (3): 465–474. doi:10.1006/jcss.1997.1490.
↑ Vazirani, Vijay V. (2003). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.
↑ H. Kellerer; U. Pferschy; D. Pisinger (2004). बस्ता समस्याएँ. Springer.
↑ ^6.0 ^6.1 ^6.2 ^6.3 Woeginger, Gerhard J. (2000-02-01). "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?". INFORMS Journal on Computing. 12 (1): 57–74. doi:10.1287/ijoc.12.1.57.11901. ISSN 1091-9856.
↑ Ibarra, Oscar H.; Kim, Chul E. (1975-10-01). "नैपसैक और सबसेट समस्याओं के योग के लिए तेज़ सन्निकटन एल्गोरिदम". Journal of the ACM. 22 (4): 463–468. doi:10.1145/321906.321909. ISSN 0004-5411. S2CID 14619586.
↑ Lawler, Eugene L. (1979-11-01). "नैपसेक समस्याओं के लिए तेज़ सन्निकटन एल्गोरिदम". Mathematics of Operations Research. 4 (4): 339–356. doi:10.1287/moor.4.4.339. ISSN 0364-765X. S2CID 7655435.
↑ Rhee, Donguk (2015). नैपसैक समस्याओं के लिए तेज़ पूर्णतः बहुपद सन्निकटन योजनाएँ (Thesis thesis). Massachusetts Institute of Technology. hdl:1721.1/98564.
↑ Lawler, Eugene L. (1977-01-01), Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), "A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X", Annals of Discrete Mathematics, Studies in Integer Programming (in English), Elsevier, vol. 1, pp. 331–342, doi:10.1016/S0167-5060(08)70742-8, retrieved 2021-12-17
↑ Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980-07-01). "Deterministic Production Planning: Algorithms and Complexity". Management Science. 26 (7): 669–679. doi:10.1287/mnsc.26.7.669. ISSN 0025-1909.
↑ Lawler, E. L. (1982-12-01). "संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना". Operations Research Letters (in English). 1 (6): 207–208. doi:10.1016/0167-6377(82)90022-0. ISSN 0167-6377.
↑ van Hoesel, C. P. M.; Wagelmans, Albert (1997-01-01). "एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं" (in English). {{cite journal}}: Cite journal requires |journal= (help)
↑ Cai, X. (1995-09-21). "एकल मशीन प्रणालियों में सहमत रूप से भारित विचरण को न्यूनतम करना". European Journal of Operational Research (in English). 85 (3): 576–592. doi:10.1016/0377-2217(93)E0367-7. ISSN 0377-2217.
↑ Woeginger, Gerhard J. (1999-05-01). "एक ही मशीन पर सहमत रूप से भारित भिन्नता को न्यूनतम करने के लिए एक अनुमान योजना". INFORMS Journal on Computing. 11 (2): 211–216. doi:10.1287/ijoc.11.2.211. ISSN 1091-9856.
↑ Vazirani, Vijay (2001). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 69–70. ISBN 3540653678. OCLC 47097680.
↑ Kellerer, Hans; Pferschy, Ulrich (2004-03-01). "नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग". Journal of Combinatorial Optimization (in English). 8 (1): 5–11. doi:10.1023/B:JOCO.0000021934.29833.6b. ISSN 1573-2886. S2CID 36474745.
↑ Jin, Ce (2019). 0-1 नैपसेक के लिए एक बेहतर एफपीटीएएस. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 132. pp. 76:1–76:14. arXiv:1904.09562. doi:10.4230/LIPIcs.ICALP.2019.76. ISBN 9783959771092. S2CID 128317990.
↑ Jansen, Klaus; Kraft, Stefan E. J. (2018-02-01). "अनबाउंडेड नैपसैक समस्या के लिए एक तेज़ एफपीटीएएस". European Journal of Combinatorics. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller (in English). 68: 148–174. arXiv:1504.04650. doi:10.1016/j.ejc.2017.07.016. ISSN 0195-6698. S2CID 9557898.
↑ Gribanov, D. V. (2021-05-10). "An FPTAS for the $$\var Delta $$-Modular Multidimensional Knapsack Problem". गणितीय अनुकूलन सिद्धांत और संचालन अनुसंधान. Lecture Notes in Computer Science. Vol. 12755. pp. 79–95. arXiv:2103.07257. doi:10.1007/978-3-030-77876-7_6. ISBN 978-3-030-77875-0. S2CID 232222954.
↑ Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01). "Implementing an efficient fptas for the 0–1 multi-objective knapsack problem". European Journal of Operational Research (in English). 198 (1): 47–56. doi:10.1016/j.ejor.2008.07.047. ISSN 0377-2217.
↑ Holzhauser, Michael; Krumke, Sven O. (2017-10-01). "पैरामीट्रिक नैपसेक समस्या के लिए एक एफपीटीएएस". Information Processing Letters (in English). 126: 43–47. arXiv:1701.07822. doi:10.1016/j.ipl.2017.06.006. ISSN 0020-0190. S2CID 1013794.
↑ Xu, Zhou (2012-04-16). "सममित द्विघात नैपसैक समस्या के लिए एक प्रबल बहुपद FPTAS". European Journal of Operational Research (in English). 218 (2): 377–381. doi:10.1016/j.ejor.2011.10.049. ISSN 0377-2217.
↑ Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (2011-10-01). "An FPTAS for #Knapsack and Related Counting Problems". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 817–826. doi:10.1109/FOCS.2011.32. ISBN 978-0-7695-4571-4. S2CID 5691574.
↑ Ergun, Funda; Sinha, Rakesh; Zhang, Lisa (2002-09-15). "प्रतिबंधित सबसे छोटे पथ के लिए एक बेहतर एफपीटीएएस". Information Processing Letters (in English). 83 (5): 287–291. doi:10.1016/S0020-0190(02)00205-3. ISSN 0020-0190.
↑ Tsaggouris, George; Zaroliagis, Christos (2009-06-01). "Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications". Theory of Computing Systems (in English). 45 (1): 162–186. doi:10.1007/s00224-007-9096-4. ISSN 1433-0490. S2CID 13010023.
↑ Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (2013-12-18), "A Simple FPTAS for Counting Edge Covers", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 341–348, arXiv:1309.6115, doi:10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID 14598468, retrieved 2021-12-13
↑ Kel’manov, A. V.; Romanchenko, S. M. (2014-07-01). "वेक्टर उपसमुच्चय खोज समस्या के लिए एक FPTAS". Journal of Applied and Industrial Mathematics (in English). 8 (3): 329–336. doi:10.1134/S1990478914030041. ISSN 1990-4797. S2CID 96437935.
↑ Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "विकासवादी एल्गोरिदम और गतिशील प्रोग्रामिंग". Theoretical Computer Science (in English). 412 (43): 6020–6035. doi:10.1016/j.tcs.2011.07.024. ISSN 0304-3975.

बाहरी संबंध

Complexity Zoo: FPTAS

[1] 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.

[Jansen3-2] Jansen, Thomas (1998), "Introduction to the Theory of Complexity and Approximation Algorithms", in Mayr, Ernst W.; Prömel, Hans Jürgen; Steger, Angelika (eds.), Lectures on Proof Verification and Approximation Algorithms, Springer, pp. 5–28, doi:10.1007/BFb0053011, ISBN 9783540642015. See discussion following Definition 1.30 on p. 20.

[3] Cai, Liming; Chen, Jianer (June 1997). "फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर". Journal of Computer and System Sciences (in English). 54 (3): 465–474. doi:10.1006/jcss.1997.1490.

[vvv-4] Vazirani, Vijay V. (2003). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8.

[5] H. Kellerer; U. Pferschy; D. Pisinger (2004). बस्ता समस्याएँ. Springer.

[:0-6] 6.0 ^6.1 ^6.2 ^6.3 Woeginger, Gerhard J. (2000-02-01). "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?". INFORMS Journal on Computing. 12 (1): 57–74. doi:10.1287/ijoc.12.1.57.11901. ISSN 1091-9856.

[7] Ibarra, Oscar H.; Kim, Chul E. (1975-10-01). "नैपसैक और सबसेट समस्याओं के योग के लिए तेज़ सन्निकटन एल्गोरिदम". Journal of the ACM. 22 (4): 463–468. doi:10.1145/321906.321909. ISSN 0004-5411. S2CID 14619586.

[8] Lawler, Eugene L. (1979-11-01). "नैपसेक समस्याओं के लिए तेज़ सन्निकटन एल्गोरिदम". Mathematics of Operations Research. 4 (4): 339–356. doi:10.1287/moor.4.4.339. ISSN 0364-765X. S2CID 7655435.

[9] Rhee, Donguk (2015). नैपसैक समस्याओं के लिए तेज़ पूर्णतः बहुपद सन्निकटन योजनाएँ (Thesis thesis). Massachusetts Institute of Technology. hdl:1721.1/98564.

[10] Lawler, Eugene L. (1977-01-01), Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), "A "Pseudopolynomial" Algorithm for Sequencing Jobs to Minimize Total Tardiness**Research supported by National Science Foundation Grant GJ-43227X", Annals of Discrete Mathematics, Studies in Integer Programming (in English), Elsevier, vol. 1, pp. 331–342, doi:10.1016/S0167-5060(08)70742-8, retrieved 2021-12-17

[11] Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1980-07-01). "Deterministic Production Planning: Algorithms and Complexity". Management Science. 26 (7): 669–679. doi:10.1287/mnsc.26.7.669. ISSN 0025-1909.

[12] Lawler, E. L. (1982-12-01). "संपूर्ण विलंबता समस्या के लिए एक पूर्णतः बहुपद सन्निकटन योजना". Operations Research Letters (in English). 1 (6): 207–208. doi:10.1016/0167-6377(82)90022-0. ISSN 0167-6377.

[13] van Hoesel, C. P. M.; Wagelmans, Albert (1997-01-01). "एकल-आइटम कैपेसिटेटेड आर्थिक लॉट-साइजिंग समस्याओं के लिए पूरी तरह से बहुपद अनुमान योजनाएं" (in English). {{cite journal}}: Cite journal requires |journal= (help)

[14] Cai, X. (1995-09-21). "एकल मशीन प्रणालियों में सहमत रूप से भारित विचरण को न्यूनतम करना". European Journal of Operational Research (in English). 85 (3): 576–592. doi:10.1016/0377-2217(93)E0367-7. ISSN 0377-2217.

[15] Woeginger, Gerhard J. (1999-05-01). "एक ही मशीन पर सहमत रूप से भारित भिन्नता को न्यूनतम करने के लिए एक अनुमान योजना". INFORMS Journal on Computing. 11 (2): 211–216. doi:10.1287/ijoc.11.2.211. ISSN 1091-9856.

[16] Vazirani, Vijay (2001). सन्निकटन एल्गोरिदम. Berlin: Springer. pp. 69–70. ISBN 3540653678. OCLC 47097680.

[17] Kellerer, Hans; Pferschy, Ulrich (2004-03-01). "नैपसैक समस्या के लिए एफपीटीएएस के संबंध में बेहतर गतिशील प्रोग्रामिंग". Journal of Combinatorial Optimization (in English). 8 (1): 5–11. doi:10.1023/B:JOCO.0000021934.29833.6b. ISSN 1573-2886. S2CID 36474745.

[18] Jin, Ce (2019). 0-1 नैपसेक के लिए एक बेहतर एफपीटीएएस. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 132. pp. 76:1–76:14. arXiv:1904.09562. doi:10.4230/LIPIcs.ICALP.2019.76. ISBN 9783959771092. S2CID 128317990.

[19] Jansen, Klaus; Kraft, Stefan E. J. (2018-02-01). "अनबाउंडेड नैपसैक समस्या के लिए एक तेज़ एफपीटीएएस". European Journal of Combinatorics. Combinatorial Algorithms, Dedicated to the Memory of Mirka Miller (in English). 68: 148–174. arXiv:1504.04650. doi:10.1016/j.ejc.2017.07.016. ISSN 0195-6698. S2CID 9557898.

[20] Gribanov, D. V. (2021-05-10). "An FPTAS for the $$\var Delta $$-Modular Multidimensional Knapsack Problem". गणितीय अनुकूलन सिद्धांत और संचालन अनुसंधान. Lecture Notes in Computer Science. Vol. 12755. pp. 79–95. arXiv:2103.07257. doi:10.1007/978-3-030-77876-7_6. ISBN 978-3-030-77875-0. S2CID 232222954.

[21] Bazgan, Cristina; Hugot, Hadrien; Vanderpooten, Daniel (2009-10-01). "Implementing an efficient fptas for the 0–1 multi-objective knapsack problem". European Journal of Operational Research (in English). 198 (1): 47–56. doi:10.1016/j.ejor.2008.07.047. ISSN 0377-2217.

[22] Holzhauser, Michael; Krumke, Sven O. (2017-10-01). "पैरामीट्रिक नैपसेक समस्या के लिए एक एफपीटीएएस". Information Processing Letters (in English). 126: 43–47. arXiv:1701.07822. doi:10.1016/j.ipl.2017.06.006. ISSN 0020-0190. S2CID 1013794.

[23] Xu, Zhou (2012-04-16). "सममित द्विघात नैपसैक समस्या के लिए एक प्रबल बहुपद FPTAS". European Journal of Operational Research (in English). 218 (2): 377–381. doi:10.1016/j.ejor.2011.10.049. ISSN 0377-2217.

[24] Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovic, Daniel; Vempala, Santosh; Vigoda, Eric (2011-10-01). "An FPTAS for #Knapsack and Related Counting Problems". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 817–826. doi:10.1109/FOCS.2011.32. ISBN 978-0-7695-4571-4. S2CID 5691574.

[25] Ergun, Funda; Sinha, Rakesh; Zhang, Lisa (2002-09-15). "प्रतिबंधित सबसे छोटे पथ के लिए एक बेहतर एफपीटीएएस". Information Processing Letters (in English). 83 (5): 287–291. doi:10.1016/S0020-0190(02)00205-3. ISSN 0020-0190.

[26] Tsaggouris, George; Zaroliagis, Christos (2009-06-01). "Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with Applications". Theory of Computing Systems (in English). 45 (1): 162–186. doi:10.1007/s00224-007-9096-4. ISSN 1433-0490. S2CID 13010023.

[27] Lin, Chengyu; Liu, Jingcheng; Lu, Pinyan (2013-12-18), "A Simple FPTAS for Counting Edge Covers", Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, Society for Industrial and Applied Mathematics, pp. 341–348, arXiv:1309.6115, doi:10.1137/1.9781611973402.25, ISBN 978-1-61197-338-9, S2CID 14598468, retrieved 2021-12-13

[28] Kel’manov, A. V.; Romanchenko, S. M. (2014-07-01). "वेक्टर उपसमुच्चय खोज समस्या के लिए एक FPTAS". Journal of Applied and Industrial Mathematics (in English). 8 (3): 329–336. doi:10.1134/S1990478914030041. ISSN 1990-4797. S2CID 96437935.

[29] Doerr, Benjamin; Eremeev, Anton; Neumann, Frank; Theile, Madeleine; Thyssen, Christian (2011-10-07). "विकासवादी एल्गोरिदम और गतिशील प्रोग्रामिंग". Theoretical Computer Science (in English). 412 (43): 6020–6035. doi:10.1016/j.tcs.2011.07.024. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

@@ Line 1: / Line 1: @@
-पूर्ण बहुपद-समय सन्निकटन योजना (एफपीटीएएस) फ़ंक्शन समस्याओं, विशेष रूप से [[अनुकूलन समस्या]]ओं के अनुमानित समाधान खोजने के लिए एक [[कलन विधि]] है। एक FPTAS इनपुट के रूप में समस्या का एक उदाहरण और एक पैरामीटर ε > 0 लेता है। यह आउटपुट के रूप में कम से कम एक मान लौटाता है <math>1-\epsilon</math> सही मान का गुना, और अधिक से अधिक <math>1 + \epsilon</math> सही मान का गुना.
+एक पूरी तरह से पॉलिनोमियल-समय आपकर्षण योजना (FPTAS) एक [[कलन विधि|ऐल्गोरिथ्म]] होता है जिसका उद्देश्य संवाद समस्याओं, विशेषकर [[अनुकूलन समस्या|अनुकुलन समस्याओं]], के आपूर्तिकरण समाधान के आस-पास समाधान खोजना होता है। FPTAS को प्रॉब्लम की एक इंस्टेंस और पैरामीटर ε > 0 के रूप में इनपुट मिलता है। यह सही मान की कम से कम <math>1-\epsilon</math> गुना और अधिकतम <math>1 + \epsilon</math> गुना की मान देता है, जो कि सही मान से होते हैं।
-अनुकूलन समस्याओं के संदर्भ में, सही मूल्य को इष्टतम समाधान का मूल्य समझा जाता है, और अक्सर यह निहित होता है कि एफपीटीएएस को एक वैध समाधान उत्पन्न करना चाहिए (और केवल समाधान का मूल्य नहीं)। किसी मान को वापस करना और उस मान के साथ समाधान ढूंढना यह मानने के बराबर है कि समस्या में [[स्वयं कम करने की क्षमता]] है।
+अनुकूलन समस्याओं के संदर्भ में, सही मान को विकल्प समाधान की मान के रूप में समझा जाता है, और यह अक्सर इस संदर्भ में समझा जाता है कि एक FPTAS को एक वैध समाधान प्रस्तुत करना चाहिए (और केवल समाधान की मान नहीं)। एक मान प्रस्तुत करना और उस मान के साथ एक समाधान प्राप्त करना उस समस्या की [[स्वयं कम करने की क्षमता|स्व-पुनर्निर्धारणीयता]] का अभिवादन करते हुए समान होते हैं।
-महत्वपूर्ण बात यह है कि एफपीटीएएस का रन-टाइम समस्या आकार और 1/ε में बहुपद है। यह सामान्य [[बहुपद-समय सन्निकटन योजना]] (पीटीएएस) के विपरीत है। सामान्य पीटीएएस का रन-टाइम प्रत्येक विशिष्ट ε के लिए समस्या आकार में बहुपद है, लेकिन 1/ε में घातीय हो सकता है।<ref>G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. ''Complexity and Approximation: Combinatorial optimization problems and their approximability properties'', Springer-Verlag, 1999.</ref>
-एफपीटीएएस शब्द का उपयोग एफपीटीएएस वाली समस्याओं के वर्ग को संदर्भित करने के लिए भी किया जा सकता है। एफपीटीएएस पीटीएएस का एक उपसमुच्चय है, और जब तक पी = एनपी समस्या नहीं है|पी = एनपी, यह एक सख्त उपसमुच्चय है।<ref name="Jansen3">{{citation|last=Jansen|first=Thomas|title=Lectures on Proof Verification and Approximation Algorithms|pages=5–28|year=1998|editor1-last=Mayr|editor1-first=Ernst W.|contribution=Introduction to the Theory of Complexity and Approximation Algorithms|publisher=Springer|doi=10.1007/BFb0053011|isbn=9783540642015|editor2-last=Prömel|editor2-first=Hans Jürgen|editor3-last=Steger|editor3-first=Angelika|editor3-link=Angelika Steger}}. See discussion following Definition 1.30 on [https://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA20 p.&nbsp;20].</ref>
+महत्वपूर्ण बात यह है कि एक FPTAS का रनटाइम समस्या के आकार और 1/ε में पॉलिनोमियल होता है। यह एक सामान्य [[बहुपद-समय सन्निकटन योजना|पॉलिनोमियल-समय आपकर्षण योजना]] (PTAS) के विपरीत है। एक सामान्य 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>
+FPTAS शब्द का उपयोग उन समस्याओं के संदर्भ में भी किया जा सकता है जिनके पास एक FPTAS हो। FPTAS PTAS की एक उपसमूह है, और जब तक 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>
+FPTAS में सभी समस्याएँ मानक पैरामीटरीकरण के संदर्भ में निश्चित पैरामीटर संवाद्य हैं।<ref>{{Cite journal |last1=Cai |first1=Liming |last2=Chen |first2=Jianer |date=June 1997 |title=फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी और एनपी ऑप्टिमाइज़ेशन समस्याओं की अनुमानितता पर|journal=Journal of Computer and System Sciences |language=en |volume=54 |issue=3 |pages=465–474 |doi=10.1006/jcss.1997.1490|doi-access=free }}</ref>
-बहुपद रूप से बंधे उद्देश्य फ़ंक्शन के साथ किसी भी [[दृढ़ता से एनपी-पूर्ण]] | दृढ़ता से एनपी-हार्ड अनुकूलन समस्या में एफपीटीएएस नहीं हो सकता है जब तक कि पी = एनपी न हो।<ref name="vvv">{{cite book|last=Vazirani|first=Vijay V.|title=सन्निकटन एल्गोरिदम|publisher=Springer|year=2003|isbn=3-540-65367-8|location=Berlin|pages=294–295}}</ref> हालाँकि, उलटा विफल रहता है: उदा. यदि पी, एनपी के बराबर नहीं है, तो नैपसैक समस्याओं की सूची#एकाधिक बाधाएं दृढ़ता से एनपी-हार्ड नहीं हैं, लेकिन इष्टतम उद्देश्य बहुपद रूप से बंधे होने पर भी कोई एफपीटीएएस नहीं है।<ref>{{cite book|title=बस्ता समस्याएँ|publisher=Springer|year=2004|author1=H. Kellerer |author2=U. Pferschy |author3=D. Pisinger }}</ref>
+किसी भी पॉलिनोमियल बाउंडेड उद्देश्य कार्य के साथ कोई भी [[दृढ़ता से एनपी-पूर्ण|मजबूत NP-कठिन]] अनुकुलन समस्या FPTAS नहीं हो सकता, जब तक 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-कठिन नहीं है, लेकिन जब तक आदर्श उद्देश्य पॉलिनोमियल बाउंडेड नहीं हो, तो उसका कोई FPTAS नहीं है।<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> [[गतिशील प्रोग्रामिंग]] के एक निश्चित वर्ग को एफपीटीएएस में परिवर्तित करने के लिए एक सामान्य योजना प्रस्तुत की गई।
+वेगिंगर<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> ने एक ऐसे विशेष श्रेणी के [[गतिशील प्रोग्रामिंग]] को एक FPTAS में बदलने के लिए एक सामान्य योजना प्रस्तुत की।
 === इनपुट ===
-यह योजना अनुकूलन समस्याओं को संभालती है जिसमें इनपुट को निम्नानुसार परिभाषित किया गया है:
+यह योजना उन अनुकुलन समस्याओं को संभालती है जिनमें इनपुट निम्नलिखित तरीके से परिभाषित होता है:
-*इनपुट n वैक्टर, x से बना है<sub>1</sub>,...,एक्स<sub>n</sub>.
+*इनपुट n वेक्टरों, x1, ..., xn से बना होता है।
-* प्रत्येक इनपुट वेक्टर कुछ से बना होता है <math>a</math> गैर-ऋणात्मक पूर्णांक, कहाँ <math>a</math> इनपुट पर निर्भर हो सकता है.
+* प्रत्येक इनपुट वेक्टर किसी <math>a</math> गैर-नकारात्मक पूर्णांकों से बना होता है, जहाँ <math>a</math> इनपुट पर निर्भर कर सकता है।
-* इनपुट वैक्टर के सभी घटक बाइनरी में एन्कोड किए गए हैं। तो समस्या का आकार O(n+log(X)) है, जहां X सभी वैक्टरों में सभी घटकों का योग है।
+* इनपुट वेक्टरों के सभी घटक बाइनरी में एनकोड होते हैं। इसलिए समस्या का आकार O(n+log(X)) होता है, जहाँ X सभी वेक्टरों के सभी घटकों की योग है।
 === अत्यंत सरल गतिशील कार्यक्रम ===
-यह माना जाता है कि समस्या में राज्यों का उपयोग करते हुए एक गतिशील-प्रोग्रामिंग (डीपी) एल्गोरिदम है। प्रत्येक राज्य कुछ से बना एक वेक्टर है <math>b</math> गैर-ऋणात्मक पूर्णांक, कहाँ <math>b</math> इनपुट से स्वतंत्र है. डीपी n चरणों में काम करती है। प्रत्येक चरण i पर, यह इनपुट x को संसाधित करता है<sub>i</sub>, और राज्यों एस का एक सेट बनाता है<sub>i</sub>. प्रत्येक राज्य इनपुट x का उपयोग करके समस्या का आंशिक समाधान एन्कोड करता है<sub>1</sub>,...,एक्स<sub>i</sub>. डीपी के घटक हैं:
+माना जाता है कि समस्या में एक गतिशील-प्रोग्रामिंग (DP) एल्गोरिथ्म होता है जो स्थितियों का उपयोग करता है। प्रत्येक स्थिति एक ऐसा वेक्टर होता है जिसमें कुछ <math>b</math> गैर-नकारात्मक पूर्णांक होते हैं, जहाँ <math>b</math> इनपुट से अनबद्ध होता है। DP n कदमों में काम करता है। प्रत्येक कदम i पर, यह इनपुट xi को प्रोसेस करता है और स्थितियों का एक सेट Si बनाता है। प्रत्येक स्थिति एक अधिंश समस्या को एनकोड करती है, x1, ..., xi का उपयोग करके। DP के घटक हैं:
-* एक सेट एस<sub>0</sub> प्रारंभिक अवस्थाओं का.
+* एक प्रारंभिक स्थितियों का सेट S0।
-* संक्रमण कार्यों का एक सेट एफ। F में प्रत्येक फ़ंक्शन f एक जोड़ी (स्टेट, इनपुट) को एक नई स्थिति में मैप करता है।
+* संक्रमण समारोहों का सेट F। प्रत्येक समारोह f F में एक जोड़ी (स्थिति, इनपुट) को एक नई स्थिति में मान देता है।
-* एक उद्देश्य फ़ंक्शन जी, एक राज्य को उसके मूल्य पर मैप करता है।
+* एक उद्देश्य समारोह g, जो स्थिति को उसके मूल्य में मान देता है।
 डीपी का एल्गोरिदम है:
@@ Line 34: / Line 33: @@
 ** चलो एस<sub>k</sub>:= {f(s,x<sub>k</sub>) | एफ में एफ, एस में एस<sub>k</sub><sub>−1</sub>}
 * आउटपुट न्यूनतम/अधिकतम {g(s) | एस में एस<sub>n</sub>}.
-डीपी का रन-टाइम संभावित राज्यों की संख्या में रैखिक है। सामान्य तौर पर, यह संख्या इनपुट समस्या के आकार में घातांकीय हो सकती है: यह O(n V) में हो सकती है<sup>b</sup>), जहां V एक राज्य में प्रदर्शित होने वाला सबसे बड़ा पूर्णांक है। यदि V, O(X) में है, तो रन-टाइम O(n X) में है<sup>b</sup>), जो केवल छद्म-बहुपद समय है, क्योंकि यह समस्या आकार में घातीय है जो O(लॉग X) में है।
+डायनैमिक प्रोग्रामिंग का रनटाइम संभावित स्थितियों की संख्या में लीनियर होता है। सामान्यत: इस संख्या का आकार इनपुट समस्या के आकार में विस्तारणशील हो सकता है: यह O(n V^b) में हो सकता है, जहाँ V एक स्थिति में प्रकट होने वाले सबसे बड़े पूर्णांक है। अगर V O(X) में है, तो रनटाइम O(n X^b) में होता है, जो कि केवल प्यूडो-पॉलिनोमियल समय होता है, क्योंकि यह समस्या के आकार में विस्तारणशील होता है जो O(log X) में होता है।
-इसे बहुपद बनाने का तरीका राज्य-स्थान को छोटा करना है: प्रत्येक चरण में सभी संभावित राज्यों को रखने के बजाय, केवल राज्यों का एक उपसमूह रखें; उन राज्यों को हटा दें जो अन्य राज्यों के काफी करीब हैं। कुछ शर्तों के तहत, यह ट्रिमिंग इस तरह से की जा सकती है जिससे उद्देश्य मूल्य में बहुत अधिक बदलाव न हो।
+इसे पॉलिनोमियल बनाने का एक तरीका है स्थिति-स्थान को काट देना: प्रत्येक कदम में संभावित स्थितियों को सब नहीं रखने की जगह, केवल स्थितियों का एक सबसेट रखने की जगह; उन स्थितियों को हटा दें जो अन्य स्थितियों के "पर्याप्त नजदीक" हैं। निश्चित स्थितियों की यह कट कुछ शर्तों के तहत की जा सकती है, जिनके तहत यह किसी स्थिति की उच्चता मान में बहुत अधिक बदलाव नहीं लाता है।
-इसे औपचारिक रूप देने के लिए, हम मानते हैं कि मौजूदा समस्या में एक गैर-नकारात्मक पूर्णांक वेक्टर d = (d) है<sub>1</sub>,...,डी<sub>b</sub>), जिसे समस्या का डिग्री वेक्टर कहा जाता है। प्रत्येक वास्तविक संख्या r>1 के लिए, हम कहते हैं कि दो राज्य-वेक्टर s हैं<sub>1</sub>,एस<sub>2</sub> हैं (d,r)-बंद करें यदि, 1,...,b में प्रत्येक निर्देशांक j के लिए:  <math>r^{-d_j} \cdot s_{1,j} \leq s_{2,j} \leq r^{d_j} \cdot s_{1,j}</math> (विशेष रूप से, यदि डी<sub>j</sub>=0 कुछ j के लिए, तो <math>s_{1,j} = s_{2,j}</math>).
+इसे औपचारिकत: इसे हम मानते हैं कि समस्या के पास एक गैर-नकारात्मक पूर्णांक वेक्टर d = (d1, ..., db) है, जिसे समस्या का डिग्री वेक्टर कहा जाता है। हर वास्तविक संख्या r > 1 के लिए, हम कहते हैं कि दो स्थिति-वेक्टर s1, s2 (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 के लिए dj = 0 है, तो <math>s_{1,j} = s_{2,j}</math>)।
 कोई समस्या अत्यंत कल्याणकारी कहलाती है यदि वह निम्नलिखित तीन शर्तों को पूरा करती हो:
-# ''निकटता को संक्रमण कार्यों द्वारा संरक्षित किया जाता है'': किसी भी ''r''>1 के लिए, किसी भी संक्रमण फ़ंक्शन ''f'' के लिए ''F'' में, किसी भी इनपुट-वेक्टर ''x'' के लिए, और किन्हीं दो राज्य-वेक्टर ''s'' के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है: यदि एस<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>, फिर f(s<sub>1</sub>,x) (d,r)-f(s) के करीब है<sub>2</sub>,एक्स)।
+# निकटता संक्रिया-समारोह द्वारा संरक्षित है: किसी भी r>1 के लिए, किसी भी संक्रमण समारोह f F में, किसी भी इनपुट-वेक्टर x के लिए, और किसी भी दो स्थिति-वेक्टरों s1, s2 के लिए, निम्नलिखित सत्य है: अगर s1 s2 के लिए (d, r)-नजदीक है, तो f(s1, x) f(s2, x) के लिए (d, r)-नजदीक है।
-#*इसके लिए पर्याप्त शर्त की जाँच निम्नानुसार की जा सकती है। F में प्रत्येक फ़ंक्शन f(s,x) के लिए, और 1,...,b में प्रत्येक निर्देशांक j के लिए, f द्वारा निरूपित करें<sub>j</sub>(s,x) f का j-वां निर्देशांक। लानत होना<sub>j</sub>b+a वेरिएबल्स में एक पूर्णांक फ़ंक्शन के रूप में देखा जा सकता है। मान लीजिए कि ऐसा प्रत्येक एफ<sub>j</sub>गैर-ऋणात्मक गुणांक वाला एक बहुपद है। इसे s=(z) प्रतिस्थापित करके एकल चर z वाले बहुपद में परिवर्तित करें<sup>d1</sup>,...,z<sup>db</sup>) और x=(1,...,1). यदि z में परिणामी बहुपद की घात अधिकतम d है<sub>j</sub>, तो शर्त 1 संतुष्ट है।
+#*इसके लिए एक पर्याप्त शर्त को निम्नलिखित रूप में जांचा जा सकता है। हर फ़ंक्शन 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 पूरी होती है।
-#निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है: एक पूर्णांक G ≥ 0 मौजूद है (जो मान फ़ंक्शन g और डिग्री वेक्टर d का एक फ़ंक्शन है), जैसे कि किसी भी r>1 के लिए, और किन्हीं दो राज्य-वेक्टर s के लिए<sub>1</sub>,एस<sub>2</sub>, निम्नलिखित धारण करता है: यदि एस<sub>1</sub> (डी,आर)-एस के करीब है<sub>2</sub>, फिर: जी(एस<sub>1</sub>) ≤ आर<sup>जी</sup> · जी(एस<sub>2</sub>) (समस्याओं को न्यूनतम करने में); जी(एस<sub>1</sub>) ≥ आर<sup>(-G)</sup> · g(s<sub>2</sub>) (अधिकतमीकरण समस्याओं में)।
+#मूल्य समारोह द्वारा निकटता का संरक्षित रहना: एक पूर्णांक G ≥ 0 मौजूद है (जो मूल्य समारोह g और डिग्री वेक्टर d का एक समारोह है), ऐसा कि किसी भी r>1, और किसी भी दो स्थिति-वेक्टरों s1, s2 के लिए, निम्नलिखित सत्य है: अगर s1 s2 के लिए (d, r)-नजदीक है, तो: g(s1) ≤ rG · g(s2) (कमीकरण समस्याओं में); g(s1) ≥ r(-G) · g(s2) (अधिकतमीकरण समस्याओं में)।
-#*इसके लिए एक पर्याप्त शर्त यह है कि फ़ंक्शन g गैर-नकारात्मक गुणांक वाला एक बहुपद फ़ंक्शन (b चर का) है।
+#*इसके लिए पर्याप्त शर्त यह है कि फ़ंक्शन g एक पॉलिनोमियल फ़ंक्शन (b चरणों की) हो, जिसमें गैर-नकारात्मक संख्यात्मक हों।
 #तकनीकी शर्तें:
-#*F में सभी संक्रमण फ़ंक्शन f और मान फ़ंक्शन g का मूल्यांकन पॉलीटाइम में किया जा सकता है।
+#*सभी संक्रमण समारोह f F और मूल्य समारोह g को पॉलिटाइम में मूल्यांकित किया जा सकता है।
-#*संख्या |F| संक्रमण फलनों का n और log(X) में बहुपद है।
+#*संक्रमण समारोहों की संख्या |F| n और log(X) में पॉलिनोमियल है।
-#*सेट एस<sub>0</sub> प्रारंभिक अवस्थाओं की गणना एन और लॉग (एक्स) में समय बहुपद में की जा सकती है।
+#*प्रारंभिक स्थितियों का सेट S0 को n और log(X) में पॉलिनोमियल समय में गणना की जा सकती है।
-#*मान लीजिए वी<sub>j</sub>उन सभी मानों का समुच्चय बनें जो किसी स्थिति में निर्देशांक j में प्रकट हो सकते हैं। फिर, V में प्रत्येक मान का [[प्राकृतिक]] लघुगणक<sub>j</sub>अधिकतम एक बहुपद P है<sub>1</sub>(एन,लॉग(एक्स)).
+#*Vj को स्थिति के कोआर्डिनेट j में प्रकट होने वाले सभी मानों का सेट कहें। तब, Vj में हर मान का [[प्राकृतिक|ln]] न केवल एक पॉलिनोमियल P1(n,log(X)) में सबसे अधिक है।
-#*यदि डी<sub>j</sub>=0, वी की कार्डिनैलिटी<sub>j</sub>अधिकतम एक बहुपद P है<sub>2</sub>(एन,लॉग(एक्स)).
+#*अगर dj=0, तो Vj की कार्डिनैलिटी न केवल एक पॉलिनोमियल P2(n,log(X)) में सबसे अधिक हो सकती है।
-प्रत्येक अत्यंत-परोपकारी समस्या के लिए, गतिशील कार्यक्रम को FPTAS में परिवर्तित किया जा सकता है। परिभाषित करना:
+हर अत्यधिक दयालु समस्या के लिए, गतिशील कार्यक्रम को एक FPTAS में परिवर्तित किया जा सकता है। निर्धारित करें:
-* <math>\epsilon</math> := आवश्यक सन्निकटन अनुपात.
+* <math>\epsilon</math> := आवश्यक सन्निकटन अनुपात।
 * <math>r := 1 + \frac{\epsilon}{2 G n}</math>, जहां G स्थिति 2 से स्थिरांक है। ध्यान दें <math>\frac{1}{\ln{r}}  \leq 1 + \frac{2Gn}{\epsilon}</math>.
-* <math>L := \left\lceil \frac{P_1(n,\log(X))}{\ln(r)} \right\rceil</math>, जहां पी<sub>1</sub> स्थिति 3 से बहुपद है (प्रत्येक मान के एलएन पर एक ऊपरी सीमा जो एक राज्य वेक्टर में दिखाई दे सकती है)। ध्यान दें कि <math>L\leq \left\lceil \left(1 + \frac{2 G n}{\epsilon}\right) P_1(n, \log{X}) \right\rceil</math>, इसलिए यह इनपुट और इन के आकार में बहुपद है <math>1/\epsilon</math>. भी, <math>r^L = e^{\ln{r}}\cdot L \geq e^{P_1(n,\log{x})}</math>, तो पी की परिभाषा के अनुसार<sub>1</sub>, प्रत्येक पूर्णांक जो राज्य-वेक्टर में दिखाई दे सकता है वह सीमा [0,r<sup>एल</sup>].
+* <math>L := \left\lceil \frac{P_1(n,\log(X))}{\ln(r)} \right\rceil</math>, जहाँ P1 स्थिति 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>, इसलिए पी1 की परिभाषा के अनुसार, प्रत्येक पूर्णांक जो एक राज्य-वेक्टर में दिखाई दे सकता है वह सीमा [0,आरएएल] में है।
-* सीमा को विभाजित करें [0,r<sup>एल</sup>] में एल+1 आर-अंतराल: <math>I_0 = [0]; I_1 = [1,r); I_2 = [r,r^2); \ldots ; I_L = [r^{L-1}, r^L]</math>.
+* सीमा [0, rL] को 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>।
-* राज्य स्थान को आर-बॉक्स में विभाजित करें: प्रत्येक निर्देशांक k को डिग्री d के साथ<sub>k</sub>≥ 1 को उपरोक्त L+1 अंतराल में विभाजित किया गया है; प्रत्येक d के साथ समन्वय करता है<sub>k</sub>= 0 को P में विभाजित किया गया है<sub>2</sub>(n,log(X)) सिंगलटन अंतराल - निर्देशांक k के प्रत्येक संभावित मान के लिए एक अंतराल (जहाँ P<sub>2</sub> उपरोक्त शर्त 3 से बहुपद है)।
+* स्थिति अंतरिक्ष को r-बॉक्स में विभाजित करें: प्रत्येक निर्देशिका k जिसका डिग्री dk ≥ 1 है, विशीर्णता ऊपर L+1 अंतरालों में विभाजित किया जाता है; प्रत्येक निर्देशिका जिसका dk = 0 है, P2(n,log(X)) एकल अंतरालों में विभाजित किया जाता है - प्रत्येक संभावित मूल्य के लिए एक अंतराल (जहाँ P2 condition 3 का पॉलिनोमियल है)।
-**ध्यान दें कि प्रत्येक संभावित स्थिति बिल्कुल एक आर-बॉक्स में समाहित है; यदि दो अवस्थाएँ एक ही r-बॉक्स में हैं, तो वे (d,r)-बंद हैं।
+**ध्यान दें कि प्रत्येक संभावित स्थिति केवल एक r-बॉक्स में शामिल है; अगर दो स्थितियाँ एक ही r-बॉक्स में हैं, तो वे (d,r)-नजदीक हैं।
 *<math>R := (L + 1 + P_2(n,\log{X}))^b</math>.
-** ध्यान दें कि आर-बॉक्स की संख्या अधिकतम आर है। चूंकि बी एक निश्चित स्थिरांक है, यह आर इनपुट के आकार में बहुपद है और इसमें <math>1/\epsilon</math>.
+** ध्यान दें कि r-बॉक्स की संख्या अधिकतम R है। क्योंकि b एक निश्चित स्थिर संख्या है, इसलिए यह R इनपुट के आकार में पॉलिनोमियल और <math>1/\epsilon</math> में है।
-एफपीटीएएस डीपी के समान ही चलता है, लेकिन प्रत्येक चरण में, यह राज्य सेट को एक छोटे सेट टी में ट्रिम कर देता है<sub>k</sub>, जिसमें प्रत्येक आर-बॉक्स में बिल्कुल एक स्थिति होती है। FPTAS का एल्गोरिदम है:
+FPTAS DP के समान ढंग से चलता है, लेकिन प्रत्येक कदम में, यह स्थिति सेट को एक छोटे सेट Tk में काटता है, जो प्रत्येक r-बॉक्स में एक ही स्थिति को शामिल करता है। FPTAS की एल्गोरिथम निम्नलिखित है:
-* चलो टी<sub>0</sub> := एस<sub>0</sub> = प्रारंभिक अवस्थाओं का समुच्चय.
+* मान लीजिए T0 := S0 = प्रारंभिक अवस्थाओं का समुच्चय।
 * k = 1 से n के लिए करें:
 ** चलो यू<sub>k</sub>:= {f(s,x<sub>k</sub>) | एफ में एफ, टी में एस<sub>k</sub><sub>−1</sub>}
 **मान लीजिए टी<sub>k</sub>:= यू की एक छंटनी प्रति<sub>k</sub>: प्रत्येक आर-बॉक्स के लिए जिसमें यू के एक या अधिक राज्य शामिल हैं<sub>k</sub>, T में बिल्कुल एक अवस्था रखें<sub>k</sub>.
 * आउटपुट न्यूनतम/अधिकतम {g(s) | टी में एस<sub>n</sub>}.
-एफपीटीएएस का रन-टाइम प्रत्येक टी में संभावित राज्यों की कुल संख्या में बहुपद है<sub>i</sub>, जो कि आर-बॉक्स की कुल संख्या है, जो कि अधिकतम आर है, जो एन, लॉग (एक्स) में बहुपद है, और <math>1/\epsilon</math>.
+FPTAS का रनटाइम प्रत्येक Ti में संभावित स्थितियों की कुल संख्या में पॉलिनोमियल होता है, जो अधिकतम एकत्रित r-बॉक्स की कुल संख्या होती है, जो अधिकतम R होती है, जो पॉलिनोमियल होती है n, log(X), और <math>1/\epsilon</math> में।
-ध्यान दें, प्रत्येक राज्य के लिए<sub>u</sub>यू में<sub>k</sub>, इसका उपसमुच्चय T<sub>k</sub>इसमें कम से कम एक राज्य शामिल है<sub>t</sub>वह (डी,आर)-एस के करीब है<sub>u</sub>. साथ ही, प्रत्येक यू<sub>k</sub>एस का एक उपसमुच्चय है<sub>k</sub>मूल (बिना छंटे हुए) डीपी में। एफपीटीएएस की शुद्धता साबित करने की मुख्य विधि है:<ref name=":0" />{{Rp|page=|location=Lem.3.3}} <ब्लॉककोट>
+ध्यान दें कि प्रत्येक स्थिति su में Uk में, उसका उपसमूह Tk में कम से कम एक स्थिति st होता है जो su के (d, r)-नजदीक होता है। भी, प्रत्येक Uk प्रारंभिक (बिना काटे गए) DP के स्थिति सेट Sk की एक उपसेट है। FPTAS की सहीता की प्रमुख प्रमाण-सिद्धि निम्नलिखित है:<ref name=":0" />{{Rp|page=|location=Lem.3.3}}
-,...,n में प्रत्येक चरण k के लिए, प्रत्येक अवस्था s के लिए<sub>s</sub>एस में<sub>k</sub>, एक राज्य है s<sub>t</sub>टी में<sub>k</sub>वह है (डी,आर<sup>क</sup>)-स के करीब<sub>s</sub>. </ब्लॉककोट>
+प्रत्येक कदम k में 0,...,n, प्रत्येक स्थिति ss Sk में, एक ऐसी स्थिति st होती है जो ss के (d,rk)-नजदीक होती है।
-इसका प्रमाण k पर प्रेरण द्वारा है। K=0 के लिए हमारे पास T है<sub>k</sub>=एस<sub>k</sub>; प्रत्येक अवस्था (d,1)-स्वयं के करीब है। मान लीजिए कि लेम्मा k-1 के लिए है। प्रत्येक राज्य के लिए एस<sub>s</sub>एस में<sub>k</sub>, चलो एस<sub>s-</sub>एस में इसके पूर्ववर्तियों में से एक बनें<sub>k-1</sub>, ताकि f(s<sub>s</sub><sub>−</sub>,x)=s<sub>s</sub>. प्रेरण धारणा के अनुसार, एक राज्य है<sub>t-</sub>टी में<sub>k-1</sub>, वह है (डी,आर<sup>k-1</sup>)-s के करीब<sub>s</sub><sub>−</sub>. चूंकि निकटता संक्रमणों द्वारा संरक्षित है (ऊपर शर्त 1), एफ(एस)।<sub>t</sub><sub>−</sub>,x) है (d,r<sup>k-1</sup>)-f(s) के करीब<sub>s</sub><sub>−</sub>,x)=s<sub>s</sub>. यह एफ(एस<sub>t</sub><sub>−</sub>,x) U में है<sub>k</sub>. ट्रिमिंग के बाद, एक राज्य है एस<sub>t</sub>टी में<sub>k</sub>वह (d,r)-f(s) के करीब है<sub>t-</sub>,एक्स)। यह एस<sub>t</sub>है (डी,आर<sup>क</sup>)-स के करीब<sub>s</sub>.
+इसका प्रमाण 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) के करीब होती है। यह सेंट (डी,आरके)-एसएस के करीब है।
-अब राज्य पर विचार करें<sup>*</sup>एस में<sub>n</sub>, जो इष्टतम समाधान से मेल खाता है (अर्थात, g(s*)=OPT)। उपरोक्त लेम्मा के अनुसार, T में एक अवस्था t* है<sub>n</sub>, जो (डी,आर) है<sup>एन</sup>)-एस के करीब<sup>*</sup>. चूँकि निकटता को मान फ़ंक्शन द्वारा संरक्षित किया जाता है, g(t*) ≥ r<sup>(-Gn)</sup> · g(s*) अधिकतमीकरण समस्या के लिए। आर की परिभाषा के अनुसार, <math>r^{-Gn}\geq (1-\epsilon)</math>. इसलिए <math>g(t^*)\geq (1-\epsilon)\cdot OPT</math>. एक समान तर्क न्यूनतमकरण समस्या के लिए काम करता है।
+अब विचार करें कि स्थिति s* Sn में है, जो सर्वोत्तम समाधान का संवादना करती है (यानी, g(s*)=OPT)। उपरोक्त उपनिवेश के अनुसार, एक स्थिति t* Tn में है, जो s* के (d,rn)-नजदीक है। निकटता मूल्य समारोह द्वारा संरक्षित होती है, इसलिए एक अधिकतमीकरण समस्या के लिए g(t*) ≥ r(-Gn) · g(s*) होता है। r की परिभाषा द्वारा, <math>r^{-Gn}\geq (1-\epsilon)</math>। इस प्रकार <math>g(t^*)\geq (1-\epsilon)\cdot OPT</math> होता है। एक समान तर्क एक कमीकरण समस्या के लिए काम करता है।
 ==== उदाहरण ====
 यहां अत्यंत-परोपकारी समस्याओं के कुछ उदाहरण दिए गए हैं, जिनमें उपरोक्त प्रमेय के अनुसार FPTAS है।<ref name=":0" />
-. सबसे बड़ी राशि को न्यूनतम करने के लक्ष्य के साथ [[मल्टीवे संख्या विभाजन]] (समकक्ष, [[समान-मशीन शेड्यूलिंग]]) अत्यंत-परोपकारी है। यहां, हमारे पास a = 1 (इनपुट पूर्णांक हैं) और b = डिब्बे की संख्या (जिसे निश्चित माना जाता है)। प्रत्येक अवस्था b पूर्णांकों का एक सदिश है जो b बिन्स के योग को दर्शाता है। बी फ़ंक्शन हैं: प्रत्येक फ़ंक्शन जे अगले इनपुट को बिन जे में डालने का प्रतिनिधित्व करता है। फ़ंक्शन g(s) s का सबसे बड़ा तत्व चुनता है। एस<sub>0</sub> = {(0,...,0)}. चरम-परोपकार की शर्तें डिग्री-वेक्टर d=(1,...,1) और G=1 से संतुष्ट हैं। जब भी मशीनों की संख्या तय होती है तो परिणाम [[वर्दी-मशीन शेड्यूलिंग]] और असंबंधित-मशीन शेड्यूलिंग तक विस्तारित होता है (यह आवश्यक है क्योंकि आर - आर-बॉक्स की संख्या - बी में घातीय है)। निरूपित पीएम||<math>\max C_j</math> या Qm||<math>\max C_j</math> या आरएम||<math>\max C_j</math>.
+. [[मल्टीवे संख्या विभाजन|अनेकगुणा संख्या संविभाजन]] ([[समान-मशीन शेड्यूलिंग]] के साथ व्यक्तिगत करने की अभिलाषा के साथ) जिसका लक्ष्य सबसे बड़ी योग को कम करना है, बेहद दयालु है। यहां, हमारा a = 1 होता है (इंटीज होते हैं), और b = बिनों की संख्या (जिसे स्थिर माना जाता है)। प्रत्येक स्थिति b योगों की बिनों के योगों का प्रतिनिधित्व करने वाले b पूर्णांकों का एक वेक्टर होती है। यहाँ b की फ़ंक्शन होती हैं: प्रत्येक फ़ंक्शन j अगले इंटीज को बिन j में डालने का प्रतिनिधित्व करती है। फ़ंक्शन g(s) s के सबसे बड़े तत्व को चुनती है। S0 = {(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 पर विचार करें, जहां लक्ष्य दो भागों के योग के बीच अंतर के वर्ग को कम करना है। उसी DP का उपयोग किया जा सकता है, लेकिन इस बार मान फ़ंक्शन g(s) = (s) के साथ<sub>1</sub>-एस<sub>2</sub>)<sup>2</sup>. अब, शर्त 2 का उल्लंघन हुआ है: राज्य (एस)।<sub>1</sub>,एस<sub>1</sub>) और (एस<sub>1</sub>,एस<sub>2</sub>) हो सकता है (डी,आर)-बंद, लेकिन जी(एस)।<sub>1</sub>,एस<sub>1</sub>) = 0 जबकि g(s<sub>1</sub>,एस<sub>2</sub>) > 0. इसलिए उपरोक्त प्रमेय लागू नहीं किया जा सकता है। दरअसल, समस्या में एफपीटीएएस नहीं है जब तक कि पी=एनपी न हो, क्योंकि एफपीटीएएस का उपयोग पॉलीटाइम में यह तय करने के लिए किया जा सकता है कि इष्टतम मान 0 है या नहीं।
+* ध्यान दें: एक विशेष प्रकार की स्थिति 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 है या नहीं।
-. समान या समान मशीनों की किसी निश्चित संख्या पर घन कार्य पूरा होने के समय का योग - बाद वाले को Qm द्वारा दर्शाया गया है||<math>\sum C_j^3</math> - a=1, b=3, d=(1,1,3) के साथ पूर्व-परोपकारी है। इसे समापन समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।
+. समान या समान मशीनों की किसी भी निश्चित संख्या पर घन कार्य पूरा होने के समय का योग - Qm||<math>\sum C_j^3</math> द्वारा निरूपित बाद वाला - a=1, b=3, d=(1,1,3) के साथ पूर्व-परोपकारी है। इसे पूर्ण होने के समय की किसी भी निश्चित शक्ति तक बढ़ाया जा सकता है।
-. समान या समान मशीनों की किसी निश्चित संख्या पर भारित समापन समय का योग - बाद वाले को Qm द्वारा दर्शाया गया है||<math>\sum w_j C_j</math>.
+. समान या समान मशीनों की किसी भी निश्चित संख्या पर भारित समापन समय का योग - बाद वाले को Qm||<math>\sum w_j C_j</math> द्वारा दर्शाया गया है।
-. समय-निर्भर प्रसंस्करण समय के साथ, समान या समान मशीनों की किसी निश्चित संख्या पर पूरा होने के समय का योग: Qm|time-dep|<math>\sum C_j</math>. यह पूर्णता समय के भारित योग के लिए भी मान्य है।
+. समय-निर्भर प्रसंस्करण समय के साथ, समान या समान मशीनों की किसी भी निश्चित संख्या पर पूरा होने के समय का योग: Qm|time-dep|<math>\sum C_j</math>। यह पूरा होने के समय के भारित योग के लिए भी लागू है।
-. किसी भी निश्चित संख्या में मशीनों पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: एम||<math>\sum w_j|C_j|</math>.
+. मशीनों की किसी भी निश्चित संख्या पर एक सामान्य नियत तारीख के बारे में भारित शीघ्रता-मंदी: एम||<math>\sum w_j|C_j|</math>।
 === सरल गतिशील कार्यक्रम ===
@@ Line 98: / Line 97: @@
 सरल गतिशील प्रोग्राम उपरोक्त फॉर्मूलेशन में निम्नलिखित घटक जोड़ते हैं:
-* फ़िल्टरिंग फ़ंक्शंस का एक सेट एच, एफ के समान कार्डिनैलिटी का। प्रत्येक फ़ंक्शन एच<sub>i</sub>H में एक जोड़ी (स्टेट, इनपुट) को बूलियन मान पर मैप किया जाता है। मान सत्य होना चाहिए यदि और केवल यदि संक्रमण f को सक्रिय किया जा रहा है<sub>i</sub>इस जोड़ी पर एक वैध स्थिति का नेतृत्व होगा।
+* एक फ़िल्टरिंग फ़ंक्शनों का सेट H, जो F की तरही संख्या में होते हैं। प्रत्येक फ़ंक्शन hi H में एक जोड़ (स्थिति, इनपुट) को एक बूलियन मूल्य में चित्रित करती है। मूल्य "सत्य" तभी होना चाहिए जब और केवल जब इस जोड़ पर fi का संक्रमण किया जाएगा और यह एक मान्य स्थिति तक पहुँचाएगा।
-*एक प्रभुत्व संबंध, जो राज्यों पर एक [[आंशिक आदेश]] है (कोई उदासीनता नहीं, सभी जोड़े तुलनीय नहीं हैं), और एक अर्ध-प्रभुत्व संबंध जो राज्यों पर एक कुल पूर्व आदेश है (उदासीनता की अनुमति है, सभी जोड़े तुलनीय हैं)।
+*एक प्रदर्शन संबंध, जो स्थितियों पर एक [[आंशिक आदेश]] है (कोई समानता नहीं, सभी जोड़ों का तुलना किया नहीं जा सकता है), और एक अर्ध-प्रदर्शन संबंध, जो स्थितियों पर एक पूर्ण पूर्व-क्रम है (समानताएँ अनुमति दी जाती हैं, सभी जोड़ों की तुलना की जा सकती है)।
 मूल डीपी को इस प्रकार संशोधित किया गया है:
 *चलिए एस<sub>0</sub> := प्रारंभिक अवस्थाओं का समुच्चय.

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 19:34, 14 August 2023

Contents

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