सन्निकटन एल्गोरिथ्म

कंप्यूटर विज्ञान और संचालन अनुसंधान में, सन्निकटन कलन विधि समय जटिलता#बहुपद समय एल्गोरिदम हैं जो अनुकूलन समस्या ओं (विशेष रूप से एनपी-कठोरता में एनपी-हार्ड समस्याओं में) के लिए सन्निकटन समाधान पाते हैं, जो कि इष्टतम एक के लिए लौटे समाधान की दूरी पर साबित करने योग्य गारंटी के साथ हैं।^[1] सन्निकटन एल्गोरिदम स्वाभाविक रूप से सैद्धांतिक कंप्यूटर विज्ञान के क्षेत्र में व्यापक रूप से विश्वास किए गए पी बनाम एनपी समस्या के परिणामस्वरूप उत्पन्न होता है। पी। एनपी अनुमान।इस अनुमान के तहत, अनुकूलन समस्याओं के एक विस्तृत वर्ग को समय जटिलता में बिल्कुल हल नहीं किया जा सकता है।इसलिए, सन्निकटन एल्गोरिदम का क्षेत्र, यह समझने की कोशिश करता है कि बहुपद समय में ऐसी समस्याओं के लिए इष्टतम समाधानों को अनुमानित करना कितना संभव है।मामलों के एक भारी बहुमत में, इस तरह के एल्गोरिदम की गारंटी एक गुणक अनुपात या सन्निकटन कारक के रूप में व्यक्त की जाती है, यानी, इष्टतम समाधान हमेशा लौटे समाधान के एक (पूर्व निर्धारित) गुणक कारक के भीतर होने की गारंटी है।हालांकि, कई सन्निकटन एल्गोरिदम भी हैं जो लौटे समाधान की गुणवत्ता पर एक योजक गारंटी प्रदान करते हैं।एक सन्निकटन एल्गोरिथ्म का एक उल्लेखनीय उदाहरण जो दोनों प्रदान करता है, जान कारेल लेंस्ट्रा , डेविड शमॉयस और éva tardos का क्लासिक सन्निकटन एल्गोरिथ्म है^[2] असंबंधित समानांतर मशीनों पर शेड्यूलिंग (कम्प्यूटिंग) के लिए।

सन्निकटन एल्गोरिदम के डिजाइन और विश्लेषण में महत्वपूर्ण रूप से सबसे खराब मामले में लौटे समाधानों की गुणवत्ता को प्रमाणित करने वाला एक गणितीय प्रमाण शामिल है।^[1]यह उन्हें हेयुरिस्टिक (कंप्यूटर विज्ञान) से अलग करता है जैसे कि तैयार किए हुयी धातु पे पानी चढाने की कला या आनुवंशिक एल्गोरिदम, जो कुछ इनपुट पर यथोचित अच्छे समाधान पाते हैं, लेकिन जब वे सफल हो सकते हैं या विफल हो सकते हैं, उस पर शुरुआत में कोई स्पष्ट संकेत नहीं देते हैं।

सैद्धांतिक कंप्यूटर विज्ञान में व्यापक रुचि है कि हम उन सीमाओं को बेहतर ढंग से समझ सकें जिनसे हम कुछ प्रसिद्ध अनुकूलन समस्याओं का अनुमान लगा सकते हैं।उदाहरण के लिए, कंप्यूटर विज्ञान में लंबे समय से खुले सवालों में से एक यह निर्धारित करना है कि क्या जन्म प्रमेय है जो क्रिस्टोफाइड्स एल्गोरिथ्म से बेहतर प्रदर्शन करता है। यात्रा विक्रेता समस्या के लिए क्रिस्टोफाइड्स के 1.5 सन्निकटन एल्गोरिथ्म।सन्निकटन के दृष्टिकोण से कठिन अनुकूलन समस्याओं को समझने की इच्छा आश्चर्यजनक गणितीय कनेक्शन की खोज से प्रेरित है और कठिन अनुकूलन समस्याओं के लिए एल्गोरिदम को डिजाइन करने के लिए मोटे तौर पर लागू तकनीकों से प्रेरित है।पूर्व का एक प्रसिद्ध उदाहरण सेमीडिफ़िनाइट प्रोग्रामिंग#उदाहरण 3 (गोएमन्स-विलियम्सन अधिकतम कटौती सन्निकटन एल्गोरिथ्म) है। अधिकतम कट के लिए गोएमान्स-विलियम्सन एल्गोरिथ्म, जो उच्च आयामी ज्यामिति का उपयोग करके एक ग्राफ सिद्धांतिक समस्या को हल करता है।^[3]

परिचय

एक सन्निकटन एल्गोरिथ्म का एक सरल उदाहरण वर्टेक्स कवर समस्या के लिए एक है, जहां लक्ष्य को वर्टिस के सबसे छोटे सेट का चयन करना है जैसे कि इनपुट ग्राफ में प्रत्येक किनारे में कम से कम एक चुना हुआ वर्टेक्स होता है।वर्टेक्स कवर खोजने का एक तरीका निम्नलिखित प्रक्रिया को दोहराना है: एक खुला किनारा ढूंढें, इसके दोनों समापन बिंदुओं को कवर में जोड़ें, और सभी किनारों की घटनाओं को या तो ग्राफ से वर्टेक्स में हटा दें।जैसा कि इनपुट ग्राफ के किसी भी वर्टेक्स कवर को प्रत्येक किनारे को कवर करने के लिए एक अलग वर्टेक्स का उपयोग करना चाहिए जो प्रक्रिया में माना जाता था (चूंकि यह एक मिलान (ग्राफ सिद्धांत) बनाता है), इसलिए वर्टेक्स कवर का उत्पादन किया जाता है, इसलिए, सबसे दो बार के रूप में बड़ा होता है।इष्टतम एक।दूसरे शब्दों में, यह एक निरंतर कारक सन्निकटन एल्गोरिथ्म है जिसमें अनुमान लगाया गया है।^[4] एनपी-हार्ड समस्याएं उनके अनुमान में बहुत भिन्न होती हैं;कुछ, जैसे कि नैप्सैक समस्या, एक गुणक कारक के भीतर अनुमानित किया जा सकता है $1+\epsilon$ , किसी भी निश्चित के लिए $\epsilon >0$ , और इसलिए इष्टतम (सन्निकटन एल्गोरिदम के ऐसे परिवार को एक बहुपद समय सन्निकटन योजना या पीटीए) कहा जाता है।दूसरों को किसी भी निरंतर, या यहां तक कि बहुपद, कारक के भीतर अनुमानित करना असंभव है, जब तक कि पी = एनपी, जैसा कि क्लिक समस्या के मामले में।इसलिए, सन्निकटन एल्गोरिदम का अध्ययन करने का एक महत्वपूर्ण लाभ एनपी-पूर्णता द्वारा वहन किए गए एक से परे विभिन्न एनपी-हार्ड समस्याओं की कठिनाई का एक ठीक-ठीक वर्गीकरण है। एनपी-पूर्णता का सिद्धांत।दूसरे शब्दों में, हालांकि एनपी-पूर्ण समस्याएं सटीक समाधानों के परिप्रेक्ष्य से एक-दूसरे के बराबर (बहुपद समय में कमी के तहत) हो सकती हैं, इसी अनुकूलन समस्याएं अनुमानित समाधानों के परिप्रेक्ष्य से बहुत अलग व्यवहार करती हैं।

एल्गोरिथ्म डिजाइन तकनीक

अब तक सन्निकटन एल्गोरिदम को डिजाइन करने के लिए कई स्थापित तकनीकें हैं।इनमें निम्नलिखित शामिल हैं।

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

एक पोस्टीरियर गारंटी

जबकि सन्निकटन एल्गोरिदम हमेशा एक प्राथमिकता सबसे खराब मामले की गारंटी प्रदान करते हैं (यह additive या गुणक हो), कुछ मामलों में वे एक पोस्टीरियर गारंटी भी प्रदान करते हैं जो अक्सर बहुत बेहतर होता है।यह अक्सर एल्गोरिदम के लिए मामला होता है जो दिए गए इनपुट पर अनुकूलन समस्या के उत्तल प्रोग्रामिंग को हल करके काम करते हैं।उदाहरण के लिए, न्यूनतम वर्टेक्स कवर के लिए एक अलग सन्निकटन एल्गोरिथ्म है जो एक वर्टेक्स कवर को खोजने के लिए एक रैखिक प्रोग्रामिंग विश्राम को हल करता है जो विश्राम के मूल्य से दो बार है।चूंकि विश्राम का मूल्य इष्टतम वर्टेक्स कवर के आकार से कभी बड़ा नहीं होता है, इसलिए यह एक और 2-अनुमोदन एल्गोरिथ्म देता है।हालांकि यह पिछले सन्निकटन एल्गोरिथ्म की एक प्राथमिकता गारंटी के समान है, उत्तरार्द्ध की गारंटी बहुत बेहतर हो सकती है (वास्तव में जब एलपी छूट का मूल्य इष्टतम वर्टेक्स कवर के आकार से दूर है)।

सन्निकटन की कठोरता

एक अनुसंधान क्षेत्र के रूप में सन्निकटन एल्गोरिदम निकटता से संबंधित है और सन्निकटन की कठोरता से सूचित किया गया है, जहां कुछ सन्निकटन अनुपात के साथ कुशल एल्गोरिदम की गैर-अस्तित्व को साबित किया जाता है (व्यापक रूप से माना जाता है कि पी ≠ एनपी अनुमान))।मीट्रिक ट्रैवलिंग सेल्समैन समस्या के मामले में, सबसे अच्छी तरह से ज्ञात अनुचितता परिणाम 123/122 of 1.008196 से कम एक अनुमान अनुपात के साथ एल्गोरिदम को बाहर करता है जब तक कि पी = एनपी, करपिंस्की, लैंपिस, श्मेड।^[5] क्रिस्टोफाइड्स के 1.5 सन्निकटन एल्गोरिथ्म के अस्तित्व के ज्ञान के साथ युग्मित, यह हमें बताता है कि मीट्रिक यात्रा सेल्समैन (यदि यह मौजूद है) के लिए अनुमानितता की दहलीज 123/122 और 1.5 के बीच कहीं है।

जबकि 1970 के दशक के बाद से अनुचितता परिणाम साबित हुए हैं, इस तरह के परिणाम तदर्थ साधनों द्वारा प्राप्त किए गए थे और उस समय कोई व्यवस्थित समझ उपलब्ध नहीं थी।यह केवल स्वतंत्र सेट (ग्राफ थ्योरी) की अनुचितता पर Feige, Goldwasser, Lovász, Safra और Szegedy के 1990 के परिणाम के बाद से है^[6] और प्रसिद्ध पीसीपी प्रमेय ,^[7] अनुचित परिणाम साबित करने के लिए आधुनिक उपकरण उजागर किए गए थे।उदाहरण के लिए, पीसीपी प्रमेय से पता चलता है कि डेविड एस। जॉनसन | जॉनसन के 1974 का सन्निकटन एल्गोरिदम अधिकतम संतुष्टिदायक समस्या के लिए, कवर समस्या, स्वतंत्र सेट (ग्राफ सिद्धांत) और ग्राफ रंग सभी इष्टतम सन्निकटन अनुपात को प्राप्त करते हैं, जो कि पी ≠ एनपी मानते हैं।^[8]

व्यावहारिकता

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

अन्य मामलों में, भले ही प्रारंभिक परिणाम विशुद्ध रूप से सैद्धांतिक रुचि के हों, समय के साथ, एक बेहतर समझ के साथ, एल्गोरिदम को अधिक व्यावहारिक बनने के लिए परिष्कृत किया जा सकता है।ऐसा ही एक उदाहरण संजीव अरोड़ा (और स्वतंत्र रूप से जोसेफ एस। बी। मिशेल) द्वारा यूक्लिडियन ट्रैवलिंग सेल्समैन समस्या के लिए प्रारंभिक पीटीए है, जिसमें एक निषेधात्मक रनिंग टाइम था $n^{O(1/\epsilon )}$ के लिए $1+\epsilon$ सन्निकटन।^[9] फिर भी, एक वर्ष के भीतर इन विचारों को एक निकट-रैखिक समय में शामिल किया गया था $O(n\log n)$ किसी भी निरंतर के लिए एल्गोरिथ्म $\epsilon >0$ .^[10]

प्रदर्शन गारंटी

कुछ सन्निकटन एल्गोरिदम के लिए इष्टतम परिणाम के सन्निकटन के बारे में कुछ गुणों को साबित करना संभव है।उदाहरण के लिए, एक ρ -सन्निकटन एल्गोरिथ्म एक एल्गोरिथ्म के रूप में परिभाषित किया गया है, जिसके लिए यह साबित हो गया है कि मूल्य/लागत, f ('x' '),,अनुमानित समाधान ('x' ') एक उदाहरण के लिए' 'x' 'अधिक नहीं होगा (या कम, स्थिति के आधार पर) एक कारक की तुलना में' 'ρ' 'बार मूल्य, ऑप्ट, काएक इष्टतम समाधान।

{\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{cases}}

कारक ρ को सापेक्ष प्रदर्शन गारंटी कहा जाता है।एक सन्निकटन एल्गोरिथ्म में एक पूर्ण प्रदर्शन गारंटी या बाध्य त्रुटि c है, अगर यह प्रत्येक उदाहरण x के लिए सिद्ध किया गया है

(\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).

इसी तरह, प्रदर्शन की गारंटी, r (x, y), एक समाधान y के लिए एक उदाहरण x के रूप में परिभाषित किया गया है

R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),

जहां f (y) उदाहरण x के लिए समाधान y का मूल्य/लागत है।स्पष्ट रूप से, प्रदर्शन की गारंटी 1 से अधिक या बराबर है और 1 के बराबर है यदि और केवल यदि y एक इष्टतम समाधान है।यदि एक एल्गोरिथ्म ए (एन) के प्रदर्शन गारंटी के साथ समाधान वापस करने की गारंटी देता है, तो ए को एक आर (एन) -प्रोपॉक्सिमेशन एल्गोरिथ्म कहा जाता है और इसमें आर (एन) का अनुमान अनुपात होता है।इसी तरह, एक r (n) -Approximation एल्गोरिथ्म के साथ एक समस्या को r (n) -Approximable कहा जाता है या R (n) का अनुमान अनुपात है।^[11]^[12] कम से कम समस्याओं के लिए, दो अलग -अलग गारंटी एक ही परिणाम प्रदान करती हैं और अधिकतम समस्याओं के लिए, ρ की एक सापेक्ष प्रदर्शन गारंटी एक प्रदर्शन गारंटी के बराबर है $r=\rho ^{-1}$ ।साहित्य में, दोनों परिभाषाएँ आम हैं, लेकिन यह स्पष्ट है कि किस परिभाषा का उपयोग तब से किया जाता है, अधिकतमकरण समस्याओं के लिए, ρ of 1 जबकि r। 1।

पूर्ण प्रदर्शन की गारंटी $\mathrm {P} _{A}$ कुछ सन्निकटन एल्गोरिथ्म ए, जहां एक्स एक समस्या के एक उदाहरण को संदर्भित करता है, और जहां $R_{A}(x)$ क्या एक्स पर प्रदर्शन गारंटी है (यानी समस्या उदाहरण एक्स के लिए ρ) है:

\mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.

यह कहना है कि $\mathrm {P} _{A}$ सन्निकटन अनुपात, आर पर सबसे बड़ा बाउंड है, जो समस्या के सभी संभावित उदाहरणों पर देखता है।इसी तरह, विषम प्रदर्शन अनुपात $R_{A}^{\infty }$ है:

R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.

यह कहना है कि यह पूर्ण प्रदर्शन अनुपात के समान है, समस्या के उदाहरणों के आकार पर एक कम बाध्य एन के साथ।इन दो प्रकार के अनुपातों का उपयोग किया जाता है क्योंकि एल्गोरिदम मौजूद हैं जहां इन दोनों के बीच का अंतर महत्वपूर्ण है।

Performance guarantees
	r-approx^[11]^[12]	ρ-approx	rel. error^[12]	rel. error^[11]	norm. rel. error^[11]^[12]	abs. error^[11]^[12]
max: $f(x)\geq$	$r^{-1}\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} -c$
min: $f(x)\leq$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

एप्सिलॉन शर्तें

साहित्य में, C - ϵ (Min: C + ϵ) की अधिकतमकरण (न्यूनतमकरण) समस्या के लिए एक अनुमान अनुपात का अर्थ है कि एल्गोरिथ्म का एक अनुमानित अनुपात है, जो मनमाना ϵ> 0 के लिए C ϵ ϵ का है, लेकिन अनुपात नहीं हैϵ = 0. के लिए नहीं दिखाया जा सकता है। इसका एक उदाहरण इष्टतम अनुचितता है-सन्निकटन का अनुभवहीनता-जोहान हस्टैड के कारण संतोषजनक अधिकतम -3 एसएटी उदाहरणों के लिए 7/8 + ϵ का अनुपात।^[13] जैसा कि पहले उल्लेख किया गया है, जब c = 1, समस्या को एक बहुपद-समय सन्निकटन योजना कहा जाता है।

एक ϵ- टर्म तब दिखाई दे सकता है जब एक सन्निकटन एल्गोरिथ्म एक गुणक त्रुटि और एक निरंतर त्रुटि का परिचय देता है जबकि आकार n के उदाहरणों का न्यूनतम इष्टतम अनंत के रूप में जाता है जैसा कि n करता है।इस मामले में, कुछ स्थिरांक C और k के लिए सन्निकटन अनुपात C ∓ k / opt = c o O (1) है।मनमाना ϵ> 0 को देखते हुए, कोई भी एक बड़ा पर्याप्त n चुन सकता है जैसे कि k / opt <ϵ प्रत्येक n ≥ n के लिए <ϵ n. के लिए प्रत्येक निश्चित ϵ के लिए, आकार n <n के उदाहरणों को ब्रूट बल द्वारा हल किया जा सकता है, जिससे एक अनुमान दिखाया जा सकता हैअनुपात - एक गारंटी के साथ सन्निकटन एल्गोरिदम का अस्तित्व - प्रत्येक ϵ> 0 के लिए c ϵ ϵ का।

यह भी देखें

वर्चस्व विश्लेषण गणना किए गए समाधान के रैंक के संदर्भ में गारंटी देता है।
बहुपद -समय सन्निकटन योजना - एक प्रकार का सन्निकटन एल्गोरिथ्म जो एक पैरामीटर के रूप में सन्निकटन अनुपात लेता है
APX कुछ निरंतर-कारक सन्निकटन एल्गोरिथ्म के साथ समस्याओं का वर्ग है
सन्निकटन-संरक्षण में कमी
सटीक एल्गोरिथ्म

उद्धरण

↑ ^1.0 ^1.1 Bernard., Shmoys, David (2011). सन्निकटन एल्गोरिदम का डिजाइन. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.
↑ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "असंबंधित समानांतर मशीनों के निर्धारण के लिए सन्निकटन एल्गोरिदम". Mathematical Programming. 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708. doi:10.1007/BF01585745. ISSN 0025-5610. S2CID 206799898.
↑ Goemans, Michel X.; Williamson, David P. (November 1995). "अधिकतम कटौती और संतोषजनक समस्याओं के लिए बेहतर सन्निकटन एल्गोरिदम सेमीफाइफिनाइट प्रोग्रामिंग का उपयोग करके समस्याएं". J. ACM. 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500. doi:10.1145/227683.227684. ISSN 0004-5411. S2CID 15794408.
↑ Khot, Subhash; Regev, Oded (2008-05-01). "वर्टेक्स कवर 2 and के भीतर अनुमानित होना मुश्किल हो सकता है". Journal of Computer and System Sciences. Computational Complexity 2003. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.
↑ Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "टीएसपी के लिए नई अनुचितता सीमा". Journal of Computer and System Sciences. 81 (8): 1665–1677. arXiv:1303.6437. doi:10.1016/j.jcss.2015.06.003.
↑ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (March 1996). "इंटरैक्टिव प्रूफ और सन्निकटन क्लिक्स की कठोरता". J. ACM. 43 (2): 268–292. doi:10.1145/226643.226652. ISSN 0004-5411.
↑ Arora, Sanjeev; Safra, Shmuel (January 1998). "सबूतों की संभाव्य जाँच: एनपी का एक नया लक्षण वर्णन". J. ACM. 45 (1): 70–122. doi:10.1145/273865.273901. ISSN 0004-5411. S2CID 751563.
↑ Johnson, David S. (1974-12-01). "दहनशील समस्याओं के लिए सन्निकटन एल्गोरिदम". Journal of Computer and System Sciences. 9 (3): 256–278. doi:10.1016/S0022-0000(74)80044-9.
↑ Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. pp. 2–11. CiteSeerX 10.1.1.32.3376. doi:10.1109/SFCS.1996.548458. ISBN 978-0-8186-7594-2. S2CID 1499391. {{cite book}}: Missing or empty |title= (help)
↑ Arora, S. (October 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 554–563. doi:10.1109/SFCS.1997.646145. ISBN 978-0-8186-8197-4. S2CID 10656723. {{cite book}}: Missing or empty |title= (help)
↑ ^11.0 ^11.1 ^11.2 ^11.3 ^11.4 G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). जटिलता और सन्निकटन: कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्याएं और उनके सन्निकटन गुण.
↑ ^12.0 ^12.1 ^12.2 ^12.3 ^12.4 Viggo Kann (1992). एनपी-पूर्ण अनुकूलन समस्याओं की अनुमानितता पर (PDF).
↑ Johan Håstad (1999). "कुछ इष्टतम अनुचितता परिणाम". Journal of the ACM. 48 (4): 798–859. CiteSeerX 10.1.1.638.2808. doi:10.1145/502090.502098. S2CID 5120748.

संदर्भ

Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 978-3-540-65367-7.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
Dorit S. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
Williamson, David P.; Shmoys, David B. (April 26, 2011), The Design of Approximation Algorithms, Cambridge University Press, ISBN 978-0521195270

इस पृष्ठ में गुम आंतरिक लिंक की सूची

गतिविधि अनुसंधान
अनुमानी (कंप्यूटर विज्ञान)
अद्वितीय खेल अनुमान
स्थिर कारक सन्निकटन एल्गोरिथ्म
नस्ल की समस्या
एनपी पूर्णता
उत्तल प्रोग्रामन
रैखिक प्रोग्रामिंग छूट
कमी (जटिलता)
अनुमान की सीमा
स्वतंत्र सेट (ग्राफ सिद्धांत)
अधिकतम संतोषजनक समस्या
कवर समस्या सेट करें
अधिकतम -3SAT

बाहरी कड़ियाँ

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

| below =* सॉफ्टवेयर

}} श्रेणी: कम्प्यूटेशनल जटिलता सिद्धांत सन्निकटन एल्गोरिदम

[Bernard._2011-1] 1.0 ^1.1 Bernard., Shmoys, David (2011). सन्निकटन एल्गोरिदम का डिजाइन. Cambridge University Press. ISBN 9780521195270. OCLC 671709856.

[2] Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "असंबंधित समानांतर मशीनों के निर्धारण के लिए सन्निकटन एल्गोरिदम". Mathematical Programming. 46 (1–3): 259–271. CiteSeerX 10.1.1.115.708. doi:10.1007/BF01585745. ISSN 0025-5610. S2CID 206799898.

[3] Goemans, Michel X.; Williamson, David P. (November 1995). "अधिकतम कटौती और संतोषजनक समस्याओं के लिए बेहतर सन्निकटन एल्गोरिदम सेमीफाइफिनाइट प्रोग्रामिंग का उपयोग करके समस्याएं". J. ACM. 42 (6): 1115–1145. CiteSeerX 10.1.1.34.8500. doi:10.1145/227683.227684. ISSN 0004-5411. S2CID 15794408.

[4] Khot, Subhash; Regev, Oded (2008-05-01). "वर्टेक्स कवर 2 and के भीतर अनुमानित होना मुश्किल हो सकता है". Journal of Computer and System Sciences. Computational Complexity 2003. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.

[5] Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "टीएसपी के लिए नई अनुचितता सीमा". Journal of Computer and System Sciences. 81 (8): 1665–1677. arXiv:1303.6437. doi:10.1016/j.jcss.2015.06.003.

[6] Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (March 1996). "इंटरैक्टिव प्रूफ और सन्निकटन क्लिक्स की कठोरता". J. ACM. 43 (2): 268–292. doi:10.1145/226643.226652. ISSN 0004-5411.

[7] Arora, Sanjeev; Safra, Shmuel (January 1998). "सबूतों की संभाव्य जाँच: एनपी का एक नया लक्षण वर्णन". J. ACM. 45 (1): 70–122. doi:10.1145/273865.273901. ISSN 0004-5411. S2CID 751563.

[8] Johnson, David S. (1974-12-01). "दहनशील समस्याओं के लिए सन्निकटन एल्गोरिदम". Journal of Computer and System Sciences. 9 (3): 256–278. doi:10.1016/S0022-0000(74)80044-9.

[9] Arora, S. (October 1996). "Polynomial time approximation schemes for Euclidean TSP and other geometric problems". Proceedings of 37th Conference on Foundations of Computer Science. pp. 2–11. CiteSeerX 10.1.1.32.3376. doi:10.1109/SFCS.1996.548458. ISBN 978-0-8186-7594-2. S2CID 1499391. {{cite book}}: Missing or empty |title= (help)

[10] Arora, S. (October 1997). "Nearly linear time approximation schemes for Euclidean TSP and other geometric problems". Proceedings 38th Annual Symposium on Foundations of Computer Science. pp. 554–563. doi:10.1109/SFCS.1997.646145. ISBN 978-0-8186-8197-4. S2CID 10656723. {{cite book}}: Missing or empty |title= (help)

[ausiello99complexity-11] 11.0 ^11.1 ^11.2 ^11.3 ^11.4 G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). जटिलता और सन्निकटन: कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्याएं और उनके सन्निकटन गुण.

[kann92onthe-12] 12.0 ^12.1 ^12.2 ^12.3 ^12.4 Viggo Kann (1992). एनपी-पूर्ण अनुकूलन समस्याओं की अनुमानितता पर (PDF).

[hastad99someoptimal-13] Johan Håstad (1999). "कुछ इष्टतम अनुचितता परिणाम". Journal of the ACM. 48 (4): 798–859. CiteSeerX 10.1.1.638.2808. doi:10.1145/502090.502098. S2CID 5120748.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]