सम्मुच्चय आवरक समस्या: Difference between revisions

Revision as of 16:21, 4 July 2023

सम्मुच्चय आवरक समस्या साहचर्य, कंप्यूटर विज्ञान, संचालन अनुसंधान और संगणनात्मक जटिलता सिद्धांत में एक पारम्परिक प्रश्न है। यह कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है जिसे 1972 में एनपी-पूर्ण दिखाया गया था।

तत्व ${1, 2, \dots, n}$ का एक सम्मुच्चय (गणित) दिया गया है (समष्टि (गणित) कहा जाता है) और एक संग्रह $S$ का $m$ ऐसे सम्मुच्चय जिनका संघ (सम्मुच्चय सिद्धांत) समष्टि के बराबर है, सम्मुच्चय आवरक समस्या $S$ के सबसे छोटे उप-संग्रह की पहचान करना है जिसका संघ समष्टि के बराबर है। उदाहरण के लिए, समष्टि U = {1, 2, 3, 4, 5} और समुच्चय का संग्रह S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} } पर विचार करें। स्पष्ट रूप से S का मिलन U है। हालाँकि, हम निम्नलिखित, कम संख्या में सम्मुच्चय {{1, 2, 3}, {4, 5} } के साथ सभी तत्वों को आच्छादित कर सकते हैं।

अधिक औपचारिक रूप से, एक समष्टि ${\mathcal {U}}$ दिया गया और एक वर्ग ${\mathcal {S}}$ के उपसमुच्चय ${\mathcal {U}}$ , एक आवरण एक उपवर्ग ${\mathcal {C}}\subseteq {\mathcal {S}}$ है उन समुच्चयों का जिनका मिलन ${\mathcal {U}}$ है। निर्णय समस्या को आवरक करने वाले सम्मुच्चय में, निविष्ट एक जोड़ी $({\mathcal {U}},{\mathcal {S}})$ और एक पूर्णांक $k$ है; प्रश्न यह है कि क्या आकार का कोई निर्धारित आवरण $k$ या कम है। अनुकूलन समस्या को आवरक करने वाले सम्मुच्चय में, निविष्ट एक जोड़ी $({\mathcal {U}},{\mathcal {S}})$ है, और कार्य एक ऐसा सम्मुच्चय आवरक ढूंढना है जो सबसे कम सम्मुच्चय का उपयोग करता हो।

सम्मुच्चय आवरण का निर्णय संस्करण एनपी-पूर्ण है, और सम्मुच्चय आवरक का अनुकूलन/खोज संस्करण एनपी कठिन है। ^[1] यह एक ऐसी समस्या है जिसके अध्ययन से सन्निकटन कलन विधि के पूरे क्षेत्र के लिए मौलिक तकनीकों का विकास हुआ है।^[2] यदि प्रत्येक सम्मुच्चय को एक भार सौंपा गया है, तो यह एक भारित सम्मुच्चय आवरक समस्या बन जाती है।

पूर्णांक रैखिक कार्यक्रम सूत्रीकरण

न्यूनतम सम्मुच्चय आवरक समस्या को निम्नलिखित पूर्णांक रैखिक कार्यक्रम (आईएलपी) के रूप में तैयार किया जा सकता है।^[3]

न्यूनतमीकरण	$\sum _{s\in {\mathcal {S}}}x_{s}$		(सम्मुच्चय की संख्या कम से कम करें)
के अधीन	$\sum _{s\colon e\in s}x_{s}\geqslant 1$	for all $e\in {\mathcal {U}}$	(समष्टि के हर तत्व को समाविष्ट करें)
	$x_{s}\in \{0,1\}$	for all $s\in {\mathcal {S}}$ .	(प्रत्येक सम्मुच्चय या तो सम्मुच्चय आच्छादन में है या नहीं है)

यह आईएलपी समस्याओं को आवरक करने के लिए आईएलपी के अधिक सामान्य वर्ग से संबंधित है।

इस आईएलपी का रैखिक प्रोग्रामिंग विश्राम और अभिन्नता अंतर अधिकतम $\scriptstyle \log n$ है। यह दिखाया गया है कि इसकी रैखिक प्रोग्रामिंग छूट वास्तव में एक कारक- $\scriptstyle \log n$ न्यूनतम सम्मुच्चय आवरक समस्या के लिए सन्निकटन कलन विधि (जहाँ $\scriptstyle n$ समष्टि का आकार है) देती है। ^[4]

भारित सम्मुच्चय आवरक में, सम्मुच्चय को भार दिया जाता है। सम्मुच्चय के भार $s\in {\mathcal {S}}$ को $w_{s}$ द्वारा निरूपित करें। फिर भारित सम्मुच्चय आवरक का वर्णन करने वाला पूर्णांक रैखिक कार्यक्रम ऊपर दिए गए के समान है, अतिरिक्त इसके कि न्यूनतम करने का उद्देश्य कार्य $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$ है।

आघाती सम्मुच्चय सूत्रीकरण

सम्मुच्चय आवरण आघाती सम्मुच्चय समस्या के बराबर है। यह देखने से पता चलता है कि सम्मुच्चय आवरण के एक उदाहरण को एक स्वेच्छाचारी द्विदलीय आरेख के रूप में देखा जा सकता है, जिसमें समष्टि को बाईं ओर के शीर्षों द्वारा दर्शाया गया है, सम्मुच्चय को दाईं ओर के शीर्षों द्वारा दर्शाया गया है, और किनारों को सम्मुच्चय में तत्वों के समावेश का प्रतिनिधित्व किया गया है। फिर कार्य दाएं-शीर्षों का एक न्यूनतम गणनांक उपसमुच्चय ढूंढना है जो सभी बाएं-शीर्षों को आवरक करता है, जो वास्तव में आघाती सम्मुच्चय समस्या है।

लोलुप कलन विधि

सम्मुच्चय आवरण के बहुपद समय सन्निकटन के लिए एक लोलुप कलन विधि है जो एक नियम के अनुसार सम्मुच्चय चुनता है: प्रत्येक चरण में, वह सम्मुच्चय चुनें जिसमें सबसे बड़ी संख्या में सम्मिलित न हों। सम्मुच्चय को प्राथमिकता देने के लिए बकेट पंक्ति का उपयोग करके, इस पद्धति को निविष्ट सम्मुच्चय के आकार के योग में समय रैखिक में लागू किया जा सकता है। ^[5] यह $H(s)$ का अनुमानित अनुपात प्राप्त करता है, जहाँ $s$ आवरक किए जाने वाले सम्मुच्चय का आकार है। ^[6] दूसरे शब्दों में, यह एक ऐसा आवरण ढूंढ लेता है जो न्यूनतम एक से $H(n)$ गुना बड़ा हो सकता है, जहाँ $H(n)$ $n$ -वी हार्मोनिक संख्या है :

H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1

यह लोलुप कलन विधि वास्तव में एक सन्निकटन

H(s^{\prime })

अनुपात प्राप्त करता है जहाँ

s^{\prime }

का अधिकतम गणनांक सम्मुच्चय

S

है।

\delta -

के लिए हालाँकि, उदाहरणों के लिए, प्रत्येक

c>0

के लिए एक

c\ln {m}

सन्निकटन कलन विधि उपस्थित है। ^[7]

K=3 के साथ लोलुप कलन विधि के लिए उपयुक्त उदाहरण

एक मानक उदाहरण है जिस पर लोलुप कलन विधि अनुमानित अनुपात $\log _{2}(n)/2$ प्राप्त करता है।

समष्टि से मिलकर $n=2^{(k+1)}-2$ तत्व बना है। सम्मुच्चय प्रणाली में $k$ जोड़ीवार असंयुक्त सम्मुच्चय सम्मिलित हैं

 $S_{1},\ldots ,S_{k}$  आकार के साथ  $2,4,8,\ldots ,2^{k}$  क्रमशः, साथ ही दो अतिरिक्त असंयुक्त सम्मुच्चय  $T_{0},T_{1}$ ,

जिनमें से प्रत्येक में आधे-आधे तत्व $S_{i}$ सम्मिलित हैं इस निविष्ट पर, लोलुप कलन विधि सम्मुच्चय लेता है

$S_{k},\ldots ,S_{1}$ , उस क्रम में, जबकि इष्टतम समाधान में केवल $T_{0}$ और $T_{1}$ सम्मिलित हैं

ऐसे निविष्ट का एक उदाहरण $k=3$ दाईं ओर चित्रित है।

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

(प्रशंसनीय जटिलता धारणाओं के तहत, सम्मुच्चय अनुपयुक्तता परिणाम नीचे देखें)। लोलुप कलन विधि के लिए एक कठोर विश्लेषण से पता चलता है कि सन्निकटन अनुपात $\ln {n}-\ln {\ln {n}}+\Theta (1)$ बिल्कुल सही है। ^[8]

कम आवृत्ति प्रणाली

यदि प्रत्येक तत्व अधिकतम f सम्मुच्चय में होता है, तब बहुपद समय में एक समाधान पाया जा सकता है जो एलपी विश्राम का उपयोग करके f के एक कारक के भीतर इष्टतम का अनुमान लगाता है।

यदि पूर्णांक रैखिक कार्यक्रम में सभी ${\mathcal {S}}$ in के लिए बाधा को $x_{S}\in \{0,1\}$ $x_{S}\geq 0$ से बदल दिया जाता है। ऊपर दिखाया गया है, तो यह एक (गैर-पूर्णांक) रैखिक प्रोग्राम L बन जाता है। एल्गोरिदम को निम्नानुसार वर्णित किया जा सकता हैː

रैखिक कार्यक्रमों को हल करने की कुछ बहुपद-समय विधि का उपयोग करके प्रोग्राम L के लिए एक इष्टतम समाधान O खोजें।
वे सभी सेट S चुनें जिनके लिए संबंधित वेरिएबल x_S का समाधान O में मान कम से कम 1/f है। ^[9]

अनुपयुक्तता परिणाम

जब $n$ समष्टि के आकार को दर्शाता है, लुंड & यान्नाकाकिस (1994) ने दिखाया कि सम्मुच्चय आवरण को बहुपद समय में एक कारक ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ के भीतर अनुमानित नहीं किया जा सकता है, जब तक कि एनपी में अर्ध-बहुपद समय कलन विधि न हो। उरीएल फीगे (1998) ने इस निचली सीमा ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ में समान धारणाओं के अंतर्गत सुधार किया, जो अनिवार्य रूप से लोलुप कलन विधि द्वारा प्राप्त सन्निकटन अनुपात से मेल खाता है। रज & सफरा (1997) ) ने c\cdot \ln {n} की एक निचली सीमा स्थापित की, जहां c एक निश्चित स्थिरांक है, इस शक्तिहीन धारणा के अंतर्गत कि P≠NP है।

सी के उच्च मान के साथ एक समान परिणाम हाल ही में एलोन, मोशकोविट्ज़ और सफ़्रा (2006) द्वारा सिद्ध किया गया था। डिनूर और स्टीयरर (2013) ने यह सिद्ध करके इष्टतम अनुपयुक्तता दिखाई कि इसे ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ तक अनुमानित नहीं किया जा सकता जब तक कि P = NP न हो।

भारित सम्मुच्चय आवरक

रैखिक प्रोग्रामिंग विश्राम भारित सम्मुच्चय आवरक के लिए पूर्णांक रैखिक कार्यक्रम में कहा गया है, कोई भी $O(\log n)$ - कारक सन्निकटन प्राप्त करने के लिए यादृच्छिक गोलाई का उपयोग कर सकता है। गैर भारित सम्मुच्चय आवरक को भारित कारक के अनुसार अनुकूलित किया जा सकता है। ^[10]

↑ Korte & Vygen 2012, p. 414.
↑ Vazirani (2001, p. 15)
↑ Vazirani (2001, p. 108)
↑ Vazirani (2001, pp. 110–112)
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4
↑ Chvatal, V. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research Vol. 4, No. 3 (Aug., 1979), pp. 233-235
↑ Karpinski & Zelikovsky 1998
↑ Slavík Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441, doi:10.1145/237814.237991
↑ Vazirani (2001, pp. 118–119)
↑ Vazirani (2001, Chapter 14)
↑ Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). लाल-नीले सेट कवर समस्या पर।. United States. Dept. of Energy. OCLC 68396743.

संदर्भ

Alon, Noga; Moshkovitz, Dana; Safra, Shmuel (2006), "Algorithmic construction of sets for k-restrictions", ACM Trans. Algorithms, 2 (2): 153–177, CiteSeerX 10.1.1.138.8682, doi:10.1145/1150334.1150336, ISSN 1549-6325, S2CID 11922650.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, Cambridge, Mass.: MIT Press and McGraw-Hill, pp. 1033–1038, ISBN 978-0-262-03293-3
Feige, Uriel (1998), "A threshold of ln n for approximating set cover", Journal of the ACM, 45 (4): 634–652, CiteSeerX 10.1.1.70.5014, doi:10.1145/285055.285059, ISSN 0004-5411, S2CID 52827488.
Karpinski, Marek; Zelikovsky, Alexander (1998), "Approximating dense cases of covering problems", Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location, vol. 40, pp. 169–178, ISBN 9780821870846
Lund, Carsten; Yannakakis, Mihalis (1994), "On the hardness of approximating minimization problems", Journal of the ACM, 41 (5): 960–981, doi:10.1145/185675.306789, ISSN 0004-5411, S2CID 9021065.
Raz, Ran; Safra, Shmuel (1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP", STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM, pp. 475–484, ISBN 978-0-89791-888-6.
Dinur, Irit; Steurer, David (2013), "Analytical approach to parallel repetition", STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing, ACM, pp. 624–633.
Vazirani, Vijay V. (2001), Approximation Algorithms (PDF), Springer-Verlag, ISBN 978-3-540-65367-7
Korte, Bernhard; Vygen, Jens (2012), Combinatorial Optimization: Theory and Algorithms (5 ed.), Springer, ISBN 978-3-642-24487-2
Cardoso, Nuno; Abreu, Rui (2014), "An Efficient Distributed Algorithm for Computing Minimal Hitting Sets" (PDF), Proceedings of the 25th International Workshop on Principles of Diagnosis, Graz, Austria, doi:10.5281/zenodo.10037{{citation}}: CS1 maint: location missing publisher (link)

बाहरी संबंध

[FOOTNOTEKorteVygen2012414-1] Korte & Vygen 2012, p. 414.

[2] Vazirani (2001, p. 15)

[3] Vazirani (2001, p. 108)

[4] Vazirani (2001, pp. 110–112)

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990], "Exercise 35.3-3", Introduction to Algorithms (3rd ed.), MIT Press and McGraw-Hill, p. 1122, ISBN 0-262-03384-4

[6] Chvatal, V. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research Vol. 4, No. 3 (Aug., 1979), pp. 233-235

[7] Karpinski & Zelikovsky 1998

[8] Slavík Petr A tight analysis of the greedy algorithm for set cover. STOC'96, Pages 435-441, doi:10.1145/237814.237991

[9] Vazirani (2001, pp. 118–119)

[10] Vazirani (2001, Chapter 14)

[11] Information., Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical (1999). लाल-नीले सेट कवर समस्या पर।. United States. Dept. of Energy. OCLC 68396743.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 3: / Line 3: @@
 '''सम्मुच्चय आवरक समस्या''' [[साहचर्य]], [[कंप्यूटर विज्ञान]], संचालन अनुसंधान और [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] में एक पारम्परिक प्रश्न है। यह कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है जिसे 1972 में एनपी-पूर्ण दिखाया गया था।
-तत्व {{math|{1, 2, …, ''n''} }}का एक [[सेट (गणित)|सम्मुच्चय (गणित)]] दिया गया है ([[ब्रह्मांड (गणित)|समष्टि (गणित)]] कहा जाता है) और एक संग्रह {{mvar|S}} का {{mvar|m}} ऐसे सम्मुच्चय जिनका [[संघ (सेट सिद्धांत)|संघ (सम्मुच्चय सिद्धांत)]] समष्टि के बराबर है, सम्मुच्चय आवरक समस्या {{mvar|S}}<nowiki> के सबसे छोटे उप-संग्रह की पहचान करना है जिसका संघ समष्टि के बराबर है। उदाहरण के लिए, ब्रह्माण्ड U = {1, 2, 3, 4, 5} और समुच्चय का संग्रह S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} } पर विचार करें। स्पष्ट रूप से S का मिलन U है। हालाँकि, हम निम्नलिखित, कम संख्या में सम्मुच्चय {{1, 2, 3}, {4, 5} } के साथ सभी तत्वों को आच्छादित कर सकते हैं।</nowiki>
+तत्व {{math|{1, 2, …, ''n''} }}का एक [[सेट (गणित)|सम्मुच्चय (गणित)]] दिया गया है ([[ब्रह्मांड (गणित)|समष्टि (गणित)]] कहा जाता है) और एक संग्रह {{mvar|S}} का {{mvar|m}} ऐसे सम्मुच्चय जिनका [[संघ (सेट सिद्धांत)|संघ (सम्मुच्चय सिद्धांत)]] समष्टि के बराबर है, सम्मुच्चय आवरक समस्या {{mvar|S}}<nowiki> के सबसे छोटे उप-संग्रह की पहचान करना है जिसका संघ समष्टि के बराबर है। उदाहरण के लिए, समष्टि U = {1, 2, 3, 4, 5} और समुच्चय का संग्रह S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} } पर विचार करें। स्पष्ट रूप से S का मिलन U है। हालाँकि, हम निम्नलिखित, कम संख्या में सम्मुच्चय {{1, 2, 3}, {4, 5} } के साथ सभी तत्वों को आच्छादित कर सकते हैं।</nowiki>
 अधिक औपचारिक रूप से, एक समष्टि <math>\mathcal{U}</math> दिया गया और एक वर्ग <math>\mathcal{S}</math> के उपसमुच्चय <math>\mathcal{U}</math>, एक आवरण एक उपवर्ग <math>\mathcal{C}\subseteq\mathcal{S}</math> है उन समुच्चयों का जिनका मिलन <math>\mathcal{U}</math> है। [[निर्णय समस्या]] को आवरक करने वाले सम्मुच्चय में, निविष्ट एक जोड़ी <math>(\mathcal{U},\mathcal{S})</math> और एक पूर्णांक <math>k</math> है; प्रश्न यह है कि क्या आकार का कोई निर्धारित आवरण <math>k</math> या कम है। [[अनुकूलन समस्या]] को आवरक करने वाले सम्मुच्चय में, निविष्ट एक जोड़ी <math>(\mathcal{U},\mathcal{S})</math> है, और कार्य एक ऐसा सम्मुच्चय आवरक ढूंढना है जो सबसे कम सम्मुच्चय का उपयोग करता हो।
@@ Line 36: / Line 36: @@
 == आघाती सम्मुच्चय सूत्रीकरण ==
-सम्मुच्चय आवरण आघाती सम्मुच्चय समस्या के बराबर है। '''यह देखने से पता चलता है''' कि सम्मुच्चय आवरण कैन का एक उदाहरण है
+सम्मुच्चय आवरण आघाती सम्मुच्चय समस्या के बराबर है। यह देखने से पता चलता है कि सम्मुच्चय आवरण के एक उदाहरण को एक स्वेच्छाचारी द्विदलीय आरेख के रूप में देखा जा सकता है, जिसमें समष्टि को बाईं ओर के शीर्षों द्वारा दर्शाया गया है, सम्मुच्चय को दाईं ओर के शीर्षों द्वारा दर्शाया गया है, और किनारों को सम्मुच्चय में तत्वों के समावेश का प्रतिनिधित्व किया गया है। फिर कार्य दाएं-शीर्षों का एक न्यूनतम गणनांक उपसमुच्चय ढूंढना है जो सभी बाएं-शीर्षों को आवरक करता है, जो वास्तव में आघाती सम्मुच्चय समस्या है।
-इसे एक मनमाना [[द्विदलीय ग्राफ]] के रूप में देखा जा सकता है, जिसमें समष्टि को बाईं ओर शीर्षों द्वारा दर्शाया गया है, सम्मुच्चयों को शीर्षों द्वारा दर्शाया गया है
-दाईं ओर, और किनारे सम्मुच्चय में तत्वों को शामिल करने का प्रतिनिधित्व करते हैं। फिर कार्य दाएं-शीर्षों का एक न्यूनतम कार्डिनैलिटी उपसमुच्चय ढूंढना है जो सभी बाएं-शीर्षों को आवरक करता है, जो वास्तव में आघाती सम्मुच्चय समस्या है।
-== [[लालची एल्गोरिदम|लालची कलन विधि]] ==
+== [[लालची एल्गोरिदम|लोलुप कलन विधि]] ==
-सम्मुच्चय आवरण के बहुपद समय सन्निकटन के लिए एक लालची कलन विधि है जो एक नियम के अनुसार सम्मुच्चय चुनता है: प्रत्येक चरण में, वह सम्मुच्चय चुनें जिसमें सबसे बड़ी संख्या में शामिल न हों। सम्मुच्चय को प्राथमिकता देने के लिए बकेट कतार का उपयोग करके, इस पद्धति को निविष्ट सम्मुच्चय के आकार के योग में समय रैखिक में लागू किया जा सकता है।<ref>{{Introduction to Algorithms|edition=3|chapter=Exercise 35.3-3|pages=1122|mode=cs2}}</ref> यह का अनुमानित अनुपात प्राप्त करता है <math>H(s)</math>, कहाँ <math>s</math> आवरक किए जाने वाले सम्मुच्चय का आकार है.<ref>Chvatal, V. [https://www.jstor.org/stable/3689577 A Greedy Heuristic for the Set-Covering Problem]. Mathematics of Operations Research
+सम्मुच्चय आवरण के बहुपद समय सन्निकटन के लिए एक लोलुप कलन विधि है जो एक नियम के अनुसार सम्मुच्चय चुनता है: प्रत्येक चरण में, वह सम्मुच्चय चुनें जिसमें सबसे बड़ी संख्या में सम्मिलित न हों। सम्मुच्चय को प्राथमिकता देने के लिए बकेट पंक्ति का उपयोग करके, इस पद्धति को निविष्ट सम्मुच्चय के आकार के योग में समय रैखिक में लागू किया जा सकता है। <ref>{{Introduction to Algorithms|edition=3|chapter=Exercise 35.3-3|pages=1122|mode=cs2}}</ref> यह <math>H(s)</math> का अनुमानित अनुपात प्राप्त करता है, जहाँ <math>s</math> आवरक किए जाने वाले सम्मुच्चय का आकार है। <ref>Chvatal, V. [https://www.jstor.org/stable/3689577 A Greedy Heuristic for the Set-Covering Problem]. Mathematics of Operations Research
-Vol. 4, No. 3 (Aug., 1979), pp. 233-235</ref> दूसरे शब्दों में, यह एक ऐसा आवरण ढूंढ लेता है जो हो सकता है <math>H(n)</math> न्यूनतम एक से गुना बड़ा, जहाँ <math>H(n)</math> है <math>n</math>-वें [[हार्मोनिक संख्या]]:
+Vol. 4, No. 3 (Aug., 1979), pp. 233-235</ref> दूसरे शब्दों में, यह एक ऐसा आवरण ढूंढ लेता है जो न्यूनतम एक से <math>H(n)</math> गुना बड़ा हो सकता है, जहाँ <math>H(n)</math> <math>n</math>-वी [[हार्मोनिक संख्या]] है :
 <math display="block"> H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1</math>
-यह लालची कलन विधि वास्तव में एक सन्निकटन अनुपात प्राप्त करता है <math>H(s^\prime)</math> कहाँ <math>s^\prime</math> का अधिकतम कार्डिनैलिटी सम्मुच्चय है <math>S</math>. के लिए <math>\delta-</math>हालाँकि, घने उदाहरण मौजूद हैं <math>c \ln{m}</math>-प्रत्येक के लिए सन्निकटन एल्गोरिथ्म <math>c > 0</math>.<ref>
+यह लोलुप कलन विधि वास्तव में एक सन्निकटन <math>H(s^\prime)</math> अनुपात प्राप्त करता है जहाँ <math>s^\prime</math> का अधिकतम गणनांक सम्मुच्चय <math>S</math> है। <math>\delta-</math> के लिए हालाँकि, उदाहरणों के लिए, प्रत्येक <math>c > 0</math> के लिए एक <math>c \ln{m}</math> सन्निकटन कलन विधि उपस्थित है। <ref>
 {{harvnb|Karpinski|Zelikovsky|1998}}</ref>
-[[Image:SetCoverGreedy.gif|frame|K=3 के साथ लालची कलन विधि के लिए सटीक उदाहरण]]एक मानक उदाहरण है जिस पर लालची कलन विधि अनुमानित अनुपात प्राप्त करता है <math>\log_2(n)/2</math>.
+[[Image:SetCoverGreedy.gif|frame|K=3 के साथ लोलुप कलन विधि के लिए उपयुक्त उदाहरण]]एक मानक उदाहरण है जिस पर लोलुप कलन विधि अनुमानित अनुपात <math>\log_2(n)/2</math> प्राप्त करता है।
-ब्रह्माण्ड से मिलकर बना है <math>n=2^{(k+1)}-2</math> तत्व. सम्मुच्चय प्रणाली में शामिल हैं <math>k</math> जोड़ीवार असंयुक्त सम्मुच्चय
+समष्टि से मिलकर <math>n=2^{(k+1)}-2</math> तत्व बना है। सम्मुच्चय प्रणाली में <math>k</math> जोड़ीवार असंयुक्त सम्मुच्चय सम्मिलित हैं
   <math>S_1,\ldots,S_k</math> आकार के साथ <math>2,4,8,\ldots,2^k</math> क्रमशः, साथ ही दो अतिरिक्त असंयुक्त सम्मुच्चय <math>T_0,T_1</math>,
-जिनमें से प्रत्येक में आधे-आधे तत्व शामिल हैं <math>S_i</math>. इस निविष्ट पर, लालची कलन विधि सम्मुच्चय लेता है
+जिनमें से प्रत्येक में आधे-आधे तत्व <math>S_i</math> सम्मिलित हैं इस निविष्ट पर, लोलुप कलन विधि सम्मुच्चय लेता है
-<math>S_k,\ldots,S_1</math>, उस क्रम में, जबकि इष्टतम समाधान में केवल शामिल हैं <math>T_0</math> और <math>T_1</math>.
-ऐसे निविष्ट का एक उदाहरण <math>k=3</math> दाईं ओर चित्रित है.
+<math>S_k,\ldots,S_1</math>, उस क्रम में, जबकि इष्टतम समाधान में केवल <math>T_0</math> और <math>T_1</math> सम्मिलित हैं
+ऐसे निविष्ट का एक उदाहरण <math>k=3</math> दाईं ओर चित्रित है।
+अनुपयुक्तता परिणाम दर्शाते हैं कि लोलुप कलन विधि अनिवार्य रूप से निचले क्रम की शर्तों तक सम्मुच्चय आवरक के लिए सर्वोत्तम-संभव बहुपद समय सन्निकटन कलन विधि है।
+(प्रशंसनीय जटिलता धारणाओं के तहत, सम्मुच्चय अनुपयुक्तता परिणाम नीचे देखें)। लोलुप कलन विधि के लिए एक कठोर विश्लेषण से पता चलता है कि सन्निकटन अनुपात <math>\ln{n} - \ln{\ln{n}} + \Theta(1)</math> बिल्कुल सही है। <ref>Slavík Petr  [http://dl.acm.org/citation.cfm?id=237991 A tight analysis of the greedy algorithm for set cover]. STOC'96, Pages 435-441, {{doi|10.1145/237814.237991}}</ref>
-अनुपयुक्तता परिणाम दर्शाते हैं कि लालची कलन विधि अनिवार्य रूप से निचले क्रम की शर्तों तक सम्मुच्चय आवरक के लिए सर्वोत्तम-संभव बहुपद समय सन्निकटन कलन विधि है।
-(प्रशंसनीय जटिलता धारणाओं के तहत, सम्मुच्चय आवरक समस्या # अनुपयुक्तता परिणाम नीचे देखें)। लालची एल्गोरिथ्म के लिए एक सख्त विश्लेषण से पता चलता है कि सन्निकटन अनुपात बिल्कुल सही है <math>\ln{n} - \ln{\ln{n}} + \Theta(1)</math>.<ref>Slavík Petr  [http://dl.acm.org/citation.cfm?id=237991 A tight analysis of the greedy algorithm for set cover]. STOC'96, Pages 435-441, {{doi|10.1145/237814.237991}}</ref>
@@ Line 62: / Line 64: @@
 == कम आवृत्ति प्रणाली ==
-यदि प्रत्येक तत्व अधिकतम में होता है {{var|f}} सम्मुच्चय करता है, तो बहुपद समय में एक समाधान पाया जा सकता है जो कि एक कारक के भीतर इष्टतम का अनुमान लगाता है {{var|f}} रैखिक प्रोग्रामिंग विश्राम का उपयोग करना।
+यदि प्रत्येक तत्व अधिकतम f सम्मुच्चय में होता है, तब बहुपद समय में एक समाधान पाया जा सकता है जो एलपी विश्राम का उपयोग करके f के एक कारक के भीतर इष्टतम का अनुमान लगाता है।
-यदि बाधा <math>x_S\in\{0,1\}</math> द्वारा प्रतिस्थापित किया जाता है <math>x_S \geq 0</math> सभी के लिए {{var|S}} में <math>\mathcal{S}</math> पूर्णांक रैखिक कार्यक्रम में #पूर्णांक रैखिक कार्यक्रम सूत्रीकरण दिखाया गया है, तो यह एक (गैर-पूर्णांक) रैखिक कार्यक्रम बन जाता है {{var|L}}. एल्गोरिथ्म को इस प्रकार वर्णित किया जा सकता है:
+यदि पूर्णांक रैखिक कार्यक्रम में सभी <math>\mathcal{S}</math> in के लिए बाधा को <math>x_S\in\{0,1\}</math> <math>x_S \geq 0</math> से बदल दिया जाता है। ऊपर दिखाया गया है, तो यह एक (गैर-पूर्णांक) रैखिक प्रोग्राम {{var|L}} बन जाता है। एल्गोरिदम को निम्नानुसार वर्णित किया जा सकता हैː
-# एक इष्टतम समाधान खोजें {{var|O}} कार्यक्रम के लिए {{var|L}} रैखिक कार्यक्रमों को हल करने के लिए कुछ बहुपद-समय पद्धति का उपयोग करना।
+# रैखिक कार्यक्रमों को हल करने की कुछ बहुपद-समय विधि का उपयोग करके प्रोग्राम L के लिए एक इष्टतम समाधान O खोजें।
-# सभी सम्मुच्चय चुनें {{var|S}} जिसके लिए संगत चर {{var|x}}<sub>{{var|S}}</sub> इसका मूल्य कम से कम 1/ है{{var|f}} समाधान में {{var|O}}.<ref>{{harvtxt|Vazirani|2001|pp=118–119}}</ref>
+# वे सभी सेट {{var|S}} चुनें जिनके लिए संबंधित वेरिएबल {{var|x}}<sub>{{var|S}}</sub> का समाधान {{var|O}} में मान कम से कम 1/f है। <ref>{{harvtxt|Vazirani|2001|pp=118–119}}</ref>
 == अनुपयुक्तता परिणाम ==
-कब <math> n</math> ब्रह्माण्ड के आकार को दर्शाता है, {{harvtxt |Lund|Yannakakis|1994}} ने दिखाया कि सम्मुच्चय आवरण को बहुपद समय में एक कारक के भीतर अनुमानित नहीं किया जा सकता है <math>\tfrac{1}{2}\log_2{n} \approx 0.72\ln{n}</math>, जब तक कि एनपी में [[अर्ध-बहुपद समय]] कलन विधि न हो। [[उरीएल फीगे]] (1998) ने इस निचली सीमा में सुधार किया <math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math> समान धारणाओं के तहत, जो अनिवार्य रूप से लालची एल्गोरिथ्म द्वारा प्राप्त सन्निकटन अनुपात से मेल खाता है। {{harvtxt |Raz|Safra|1997}} एक निचली सीमा स्थापित की
+जब <math> n</math> समष्टि के आकार को दर्शाता है, {{harvtxt |लुंड|यान्नाकाकिस|1994}} ने दिखाया कि सम्मुच्चय आवरण को बहुपद समय में एक कारक <math>\tfrac{1}{2}\log_2{n} \approx 0.72\ln{n}</math> के भीतर अनुमानित नहीं किया जा सकता है, जब तक कि एनपी में [[अर्ध-बहुपद समय]] कलन विधि न हो। [[उरीएल फीगे]] (1998) ने इस निचली सीमा <math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math> में समान धारणाओं के अंतर्गत सुधार किया, जो अनिवार्य रूप से लोलुप कलन विधि द्वारा प्राप्त सन्निकटन अनुपात से मेल खाता है। {{harvtxt |रज|सफरा|1997}} ) ने c\cdot \ln {n} की एक निचली सीमा स्थापित की, जहां c एक निश्चित स्थिरांक है, इस शक्तिहीन धारणा के अंतर्गत कि P≠NP है।
-का <math>c\cdot\ln{n}</math>, कहाँ <math>c</math> एक निश्चित स्थिरांक है, इस कमज़ोर धारणा के तहत कि P<math>\not=</math>एन.पी.
-के उच्च मूल्य के साथ एक समान परिणाम <math>c</math> द्वारा हाल ही में सिद्ध किया गया {{harvtxt |Alon|Moshkovitz|Safra|2006}}. {{harvtxt |Dinur|Steurer|2013}} ने यह साबित करके इष्टतम अनुपयुक्तता दिखाई कि इसका अनुमान नहीं लगाया जा सकता <math>\bigl(1 - o(1)\bigr) \cdot \ln{n}</math> जब तक पी<math>=</math>ई.जी.
+सी के उच्च मान के साथ एक समान परिणाम हाल ही में एलोन, मोशकोविट्ज़ और सफ़्रा (2006) द्वारा सिद्ध किया गया था। डिनूर और स्टीयरर (2013) ने यह सिद्ध करके इष्टतम अनुपयुक्तता दिखाई कि इसे <math>\bigl(1 - o(1)\bigr) \cdot \ln{n}</math> तक अनुमानित नहीं किया जा सकता जब तक कि P = NP न हो।
 == भारित सम्मुच्चय आवरक ==
 {{Expand section|date=November 2017}}
-रैखिक प्रोग्रामिंग विश्राम भारित सम्मुच्चय आवरक के लिए पूर्णांक रैखिक कार्यक्रम में कहा गया है # पूर्णांक रैखिक कार्यक्रम सूत्रीकरण, कोई भी प्राप्त करने के लिए [[यादृच्छिक गोलाई]] का उपयोग कर सकता है <math>O(\log n)</math>-कारक सन्निकटन. गैर भारित सम्मुच्चय आवरक को भारित केस के अनुसार अनुकूलित किया जा सकता है।<ref>{{harvtxt|Vazirani|2001|loc=Chapter 14}}</ref>
+रैखिक प्रोग्रामिंग विश्राम भारित सम्मुच्चय आवरक के लिए पूर्णांक रैखिक कार्यक्रम में कहा गया है, कोई भी <math>O(\log n)</math> - कारक सन्निकटन प्राप्त करने के लिए [[यादृच्छिक गोलाई]] का उपयोग कर सकता है। गैर भारित सम्मुच्चय आवरक को भारित कारक के अनुसार अनुकूलित किया जा सकता है। <ref>{{harvtxt|Vazirani|2001|loc=Chapter 14}}</ref>
 ==संबंधित समस्याएँ==
 * आघाती सम्मुच्चय, सम्मुच्चय आवरक का समतुल्य पुनर्रचना है।
-* [[वर्टेक्स कवर समस्या|वर्टेक्स आवरक समस्या]] आघाती सम्मुच्चय का एक विशेष मामला है।
+* [[वर्टेक्स कवर समस्या|कोणबिंदु आवरक समस्या]] आघाती सम्मुच्चय की एक विशेष स्तिथि है।
-* [[एज कवर समस्या|एज आवरक समस्या]] सम्मुच्चय आवरक का एक विशेष मामला है।
+* [[एज कवर समस्या|एज आवरक समस्या]] सम्मुच्चय आवरक की एक विशेष स्तिथि है।
-* [[ज्यामितीय सेट कवर समस्या|ज्यामितीय सम्मुच्चय आवरक समस्या]] सम्मुच्चय आवरक का एक विशेष मामला है जब समष्टि बिंदुओं का एक सम्मुच्चय होता है <math>\mathbb{R}^d</math> और सम्मुच्चय समष्टि और ज्यामितीय आकृतियों (जैसे, डिस्क, आयत) के प्रतिच्छेदन से प्रेरित होते हैं।
+* [[ज्यामितीय सेट कवर समस्या|ज्यामितीय सम्मुच्चय आवरक समस्या]] सम्मुच्चय आवरक की एक विशेष स्तिथि है जब समष्टि बिंदुओं का एक सम्मुच्चय <math>\mathbb{R}^d</math> होता है और सम्मुच्चय समष्टि और ज्यामितीय आकृतियों (जैसे, डिस्क, आयत) के प्रतिच्छेदन से प्रेरित होते हैं।
-* [[पैकिंग सेट करें|पैकिंग सम्मुच्चय करें]]
+* [[पैकिंग सेट करें|संकुलन सम्मुच्चय करें]]
-* [[अधिकतम कवरेज समस्या|अधिकतम आवरकेज समस्या]] अधिक से अधिक तत्वों को आवरक करने के लिए अधिकतम k सम्मुच्चय चुनना है।
+* [[अधिकतम कवरेज समस्या|अधिकतम समावेशन समस्या]] अधिक से अधिक तत्वों को आवरक करने के लिए अधिकतम k सम्मुच्चय चुनना है।
-* डोमिनेटिंग सम्मुच्चय एक ग्राफ़ में शीर्षों के एक सम्मुच्चय (डोमिनेटिंग सम्मुच्चय) को इस प्रकार चुनने की समस्या है कि अन्य सभी शीर्ष [[ सेट पर दबदबा | सम्मुच्चय पर दबदबा]]  में कम से कम एक शीर्ष के निकट हों। डोमिनेटिंग सम्मुच्चय समस्या को सम्मुच्चय आवरक से कमी के माध्यम से एनपी पूर्ण दिखाया गया था।
+* बाध्यकारी सम्मुच्चय एक आरेख़ में शीर्षों के एक सम्मुच्चय (बाध्यकारी सम्मुच्चय) को इस प्रकार चुनने की समस्या है कि अन्य सभी शीर्ष[[ सेट पर दबदबा | बाध्यकारी सम्मुच्चय]] में कम से कम एक शीर्ष के निकट हों। बाध्यकारी सम्मुच्चय समस्या को सम्मुच्चय आवरक से कमी के माध्यम से एनपी पूर्ण दिखाया गया था।
-* [[सटीक कवर समस्या|सटीक आवरक समस्या]] एक ऐसे सम्मुच्चय आवरक को चुनना है जिसमें एक से अधिक आवरण सम्मुच्चय में कोई तत्व शामिल न हो।
+* [[सटीक कवर समस्या|उपयुक्त आवरक समस्या]] एक ऐसे सम्मुच्चय आवरक को चुनना है जिसमें एक से अधिक आवरण सम्मुच्चय में कोई तत्व सम्मिलित न हो।
-* लाल नीला सम्मुच्चय आवरक।<ref>{{Cite book|last=Information.|first=Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical|url=http://worldcat.org/oclc/68396743|title=लाल-नीले सेट कवर समस्या पर।|date=1999|publisher=United States. Dept. of Energy|oclc=68396743}}</ref>
+* लाल नीला सम्मुच्चय आवरक। <ref>{{Cite book|last=Information.|first=Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical|url=http://worldcat.org/oclc/68396743|title=लाल-नीले सेट कवर समस्या पर।|date=1999|publisher=United States. Dept. of Energy|oclc=68396743}}</ref>
 *[[सेट-कवर अपहरण|सम्मुच्चय-आवरक अपहरण]].

Anonymous

Search

सम्मुच्चय आवरक समस्या: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:21, 4 July 2023

Contents

पूर्णांक रैखिक कार्यक्रम सूत्रीकरण

आघाती सम्मुच्चय सूत्रीकरण

लोलुप कलन विधि

कम आवृत्ति प्रणाली

अनुपयुक्तता परिणाम

भारित सम्मुच्चय आवरक

संबंधित समस्याएँ

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सम्मुच्चय आवरक समस्या: Difference between revisions

Revision as of 16:21, 4 July 2023

पूर्णांक रैखिक कार्यक्रम सूत्रीकरण

आघाती सम्मुच्चय सूत्रीकरण

लोलुप कलन विधि

कम आवृत्ति प्रणाली

अनुपयुक्तता परिणाम

भारित सम्मुच्चय आवरक

संबंधित समस्याएँ

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories