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

Revision as of 19:56, 3 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] यदि प्रत्येक सम्मुच्चय को एक भार सौंपा गया है, तो यह एक भारित सम्मुच्चय आवरक समस्या बन जाती है।

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

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

minimize	$\sum _{s\in {\mathcal {S}}}x_{s}$		(minimize the number of sets)
subject to	$\sum _{s\colon e\in s}x_{s}\geqslant 1$	for all $e\in {\mathcal {U}}$	(cover every element of the universe)
	$x_{s}\in \{0,1\}$	for all $s\in {\mathcal {S}}$ .	(every set is either in the set cover or not)

यह आईएलपी समस्याओं को आवरक करने के लिए आईएलपी के अधिक सामान्य वर्ग से संबंधित है। इस ILP का रैखिक प्रोग्रामिंग विश्राम#अनुमान और अभिन्नता अंतर अधिकतम है $\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\ln {m}

-प्रत्येक के लिए सन्निकटन एल्गोरिथ्म

c>0

.^[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 रैखिक प्रोग्रामिंग विश्राम का उपयोग करना।

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

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

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

कब $n$ ब्रह्माण्ड के आकार को दर्शाता है, Lund & Yannakakis (1994) ने दिखाया कि सम्मुच्चय आवरकिंग को बहुपद समय में एक कारक के भीतर अनुमानित नहीं किया जा सकता है ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ , जब तक कि एनपी में अर्ध-बहुपद समय एल्गोरिदम न हो। उरीएल फीगे (1998) ने इस निचली सीमा में सुधार किया ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ समान धारणाओं के तहत, जो अनिवार्य रूप से लालची एल्गोरिथ्म द्वारा प्राप्त सन्निकटन अनुपात से मेल खाता है। Raz & Safra (1997) एक निचली सीमा स्थापित की का $c\cdot \ln {n}$ , कहाँ $c$ एक निश्चित स्थिरांक है, इस कमज़ोर धारणा के तहत कि P $\not =$ एन.पी. के उच्च मूल्य के साथ एक समान परिणाम $c$ द्वारा हाल ही में सिद्ध किया गया Alon, Moshkovitz & Safra (2006). Dinur & Steurer (2013) ने यह साबित करके इष्टतम अनुपयुक्तता दिखाई कि इसका अनुमान नहीं लगाया जा सकता ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ जब तक पी $=$ ई.जी.

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

रैखिक प्रोग्रामिंग विश्राम भारित सम्मुच्चय आवरक के लिए पूर्णांक रैखिक कार्यक्रम में कहा गया है # पूर्णांक रैखिक कार्यक्रम सूत्रीकरण, कोई भी प्राप्त करने के लिए यादृच्छिक गोलाई का उपयोग कर सकता है $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 1: / Line 1: @@
 {{Short description|Classical problem in combinatorics}}
-सेट कवर समस्या [[साहचर्य]], [[कंप्यूटर विज्ञान]], संचालन अनुसंधान और [[कम्प्यूटेशनल जटिलता सिद्धांत]] में एक शास्त्रीय प्रश्न है। यह कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है जिसे 1972 में एनपी-पूर्ण दिखाया गया था।
+सम्मुच्चय आवरक समस्या [[साहचर्य]], [[कंप्यूटर विज्ञान]], संचालन अनुसंधान और [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] में एक पारम्परिक प्रश्न है। यह कार्प की 21 एनपी-पूर्ण समस्याओं में से एक है जिसे 1972 में एनपी-पूर्ण दिखाया गया था।
-तत्वों का एक [[सेट (गणित)]] दिया गया है {{math|{1, 2, …, ''n''} }} ([[ब्रह्मांड (गणित)]] कहा जाता है) और एक संग्रह {{mvar|S}} का {{mvar|m}} ऐसे सेट जिनका [[संघ (सेट सिद्धांत)]] ब्रह्मांड के बराबर है, सेट कवर समस्या सबसे छोटे उप-संग्रह की पहचान करना है {{mvar|S}}जिसका मिलन ब्रह्माण्ड के बराबर है। उदाहरण के लिए, ब्रह्माण्ड पर विचार करें {{math|1=''U'' = {1, 2, 3, 4, 5} }} और सेट का संग्रह {{math|1=''S'' = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.}}स्पष्ट रूप से का मिलन {{mvar|S}} है {{mvar|U}}. हालाँकि, हम सभी तत्वों को निम्नलिखित, कम संख्या में सेट के साथ कवर कर सकते हैं: {{math|{ {1, 2, 3}, {4, 5} }.}}
+तत्वों {{math|{1, 2, …, ''n''} }}का एक [[सेट (गणित)|सम्मुच्चय (गणित)]] दिया गया है ([[ब्रह्मांड (गणित)]] कहा जाता है) और एक संग्रह {{mvar|S}} का {{mvar|m}} ऐसे सम्मुच्चय जिनका [[संघ (सेट सिद्धांत)|संघ (सम्मुच्चय सिद्धांत)]] ब्रह्मांड के बराबर है, सम्मुच्चय आवरक समस्या सबसे छोटे उप-संग्रह की पहचान करना है {{mvar|S}} जिसका मिलन ब्रह्माण्ड के बराबर है। उदाहरण के लिए, ब्रह्माण्ड पर विचार करें {{math|1=''U'' = {1, 2, 3, 4, 5} }} और सम्मुच्चय का संग्रह {{math|1=''S'' = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.}}स्पष्ट रूप से का मिलन {{mvar|S}} है {{mvar|U}}. हालाँकि, हम सभी तत्वों को निम्नलिखित, कम संख्या में सम्मुच्चय के साथ आवरक कर सकते हैं: {{math|{ {1, 2, 3}, {4, 5} }.}}
-अधिक औपचारिक रूप से, एक ब्रह्मांड दिया गया <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>, और कार्य एक ऐसा सेट कवर ढूंढना है जो सबसे कम सेट का उपयोग करता हो।
+अधिक औपचारिक रूप से, एक ब्रह्मांड दिया गया <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>, और कार्य एक ऐसा सम्मुच्चय आवरक ढूंढना है जो सबसे कम सम्मुच्चय का उपयोग करता हो।
-सेट कवरिंग का निर्णय संस्करण एनपी-पूर्ण है, और सेट कवर का अनुकूलन/खोज संस्करण [[ एनपी कठिन ]] है।{{sfn |Korte|Vygen|2012|p=414}} यह एक ऐसी समस्या है जिसके अध्ययन से [[सन्निकटन एल्गोरिदम]] के पूरे क्षेत्र के लिए मौलिक तकनीकों का विकास हुआ है।<ref>{{harvtxt|Vazirani|2001|p=15}}</ref> यदि प्रत्येक सेट को एक [[भार]] सौंपा गया है, तो यह एक भारित सेट कवर समस्या बन जाती है।
+सम्मुच्चय आवरकिंग का निर्णय संस्करण एनपी-पूर्ण है, और सम्मुच्चय आवरक का अनुकूलन/खोज संस्करण [[ एनपी कठिन ]] है।{{sfn |Korte|Vygen|2012|p=414}} यह एक ऐसी समस्या है जिसके अध्ययन से [[सन्निकटन एल्गोरिदम]] के पूरे क्षेत्र के लिए मौलिक तकनीकों का विकास हुआ है।<ref>{{harvtxt|Vazirani|2001|p=15}}</ref> यदि प्रत्येक सम्मुच्चय को एक [[भार]] सौंपा गया है, तो यह एक भारित सम्मुच्चय आवरक समस्या बन जाती है।
 {{Covering-Packing Problem Pairs}}
 ==[[पूर्णांक रैखिक कार्यक्रम]] सूत्रीकरण==
-न्यूनतम सेट कवर समस्या को निम्नलिखित पूर्णांक रैखिक कार्यक्रम (ILP) के रूप में तैयार किया जा सकता है।<ref>{{harvtxt|Vazirani|2001|p=108}}</ref>
+न्यूनतम सम्मुच्चय आवरक समस्या को निम्नलिखित पूर्णांक रैखिक कार्यक्रम (ILP) के रूप में तैयार किया जा सकता है।<ref>{{harvtxt|Vazirani|2001|p=108}}</ref>
 {|
 | minimize
@@ Line 29: / Line 29: @@
 | (every set is either in the set cover or not)
 |}
-यह आईएलपी समस्याओं को कवर करने के लिए आईएलपी के अधिक सामान्य वर्ग से संबंधित है।
+यह आईएलपी समस्याओं को आवरक करने के लिए आईएलपी के अधिक सामान्य वर्ग से संबंधित है।
-इस ILP का रैखिक प्रोग्रामिंग विश्राम#अनुमान और अभिन्नता अंतर अधिकतम है <math>\scriptstyle \log n</math>. यह दिखाया गया है कि इसकी रैखिक प्रोग्रामिंग छूट वास्तव में एक कारक देती है-<math>\scriptstyle \log n</math> न्यूनतम सेट कवर समस्या के लिए सन्निकटन एल्गोरिदम (जहाँ <math>\scriptstyle n</math> ब्रह्मांड का आकार है)।<ref>{{harvtxt|Vazirani|2001|pp=110–112}}</ref>
+इस ILP का रैखिक प्रोग्रामिंग विश्राम#अनुमान और अभिन्नता अंतर अधिकतम है <math>\scriptstyle \log n</math>. यह दिखाया गया है कि इसकी रैखिक प्रोग्रामिंग छूट वास्तव में एक कारक देती है-<math>\scriptstyle \log n</math> न्यूनतम सम्मुच्चय आवरक समस्या के लिए सन्निकटन एल्गोरिदम (जहाँ <math>\scriptstyle n</math> ब्रह्मांड का आकार है)।<ref>{{harvtxt|Vazirani|2001|pp=110–112}}</ref>
-भारित सेट कवर में, सेट को वजन दिया जाता है। सेट के वजन को निरूपित करें <math>s\in \mathcal{S}</math> द्वारा <math>w_{s}</math>. फिर भारित सेट कवर का वर्णन करने वाला पूर्णांक रैखिक कार्यक्रम ऊपर दिए गए के समान है, सिवाय इसके कि न्यूनतम करने का उद्देश्य कार्य है <math>\sum_{s \in \mathcal S} w_s x_s</math>.
+भारित सम्मुच्चय आवरक में, सम्मुच्चय को वजन दिया जाता है। सम्मुच्चय के वजन को निरूपित करें <math>s\in \mathcal{S}</math> द्वारा <math>w_{s}</math>. फिर भारित सम्मुच्चय आवरक का वर्णन करने वाला पूर्णांक रैखिक कार्यक्रम ऊपर दिए गए के समान है, सिवाय इसके कि न्यूनतम करने का उद्देश्य कार्य है <math>\sum_{s \in \mathcal S} w_s x_s</math>.
-== हिटिंग सेट फॉर्मूलेशन ==
+== हिटिंग सम्मुच्चय फॉर्मूलेशन ==
-सेट कवरिंग हिटिंग सेट समस्या के बराबर है। यह देखने से पता चलता है कि सेट कवरिंग कैन का एक उदाहरण है
+सम्मुच्चय आवरकिंग हिटिंग सम्मुच्चय समस्या के बराबर है। यह देखने से पता चलता है कि सम्मुच्चय आवरकिंग कैन का एक उदाहरण है
-इसे एक मनमाना [[द्विदलीय ग्राफ]] के रूप में देखा जा सकता है, जिसमें ब्रह्मांड को बाईं ओर शीर्षों द्वारा दर्शाया गया है, सेटों को शीर्षों द्वारा दर्शाया गया है
+इसे एक मनमाना [[द्विदलीय ग्राफ]] के रूप में देखा जा सकता है, जिसमें ब्रह्मांड को बाईं ओर शीर्षों द्वारा दर्शाया गया है, सम्मुच्चयों को शीर्षों द्वारा दर्शाया गया है
-दाईं ओर, और किनारे सेट में तत्वों को शामिल करने का प्रतिनिधित्व करते हैं। फिर कार्य दाएं-शीर्षों का एक न्यूनतम कार्डिनैलिटी उपसमुच्चय ढूंढना है जो सभी बाएं-शीर्षों को कवर करता है, जो वास्तव में हिटिंग सेट समस्या है।
+दाईं ओर, और किनारे सम्मुच्चय में तत्वों को शामिल करने का प्रतिनिधित्व करते हैं। फिर कार्य दाएं-शीर्षों का एक न्यूनतम कार्डिनैलिटी उपसमुच्चय ढूंढना है जो सभी बाएं-शीर्षों को आवरक करता है, जो वास्तव में हिटिंग सम्मुच्चय समस्या है।
 == [[लालची एल्गोरिदम]] ==
-सेट कवरिंग के बहुपद समय सन्निकटन के लिए एक लालची एल्गोरिदम है जो एक नियम के अनुसार सेट चुनता है: प्रत्येक चरण में, वह सेट चुनें जिसमें सबसे बड़ी संख्या में शामिल न हों। सेट को प्राथमिकता देने के लिए बकेट कतार का उपयोग करके, इस पद्धति को इनपुट सेट के आकार के योग में समय रैखिक में लागू किया जा सकता है।<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>-वें [[हार्मोनिक संख्या]]:
 <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 \ln{m}</math>-प्रत्येक के लिए सन्निकटन एल्गोरिथ्म <math>c > 0</math>.<ref>
 {{harvnb|Karpinski|Zelikovsky|1998}}</ref>
 [[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_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>\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>
 == कम आवृत्ति प्रणाली ==
-यदि प्रत्येक तत्व अधिकतम में होता है {{var|f}} सेट करता है, तो बहुपद समय में एक समाधान पाया जा सकता है जो कि एक कारक के भीतर इष्टतम का अनुमान लगाता है {{var|f}} रैखिक प्रोग्रामिंग विश्राम का उपयोग करना।
+यदि प्रत्येक तत्व अधिकतम में होता है {{var|f}} सम्मुच्चय करता है, तो बहुपद समय में एक समाधान पाया जा सकता है जो कि एक कारक के भीतर इष्टतम का अनुमान लगाता है {{var|f}} रैखिक प्रोग्रामिंग विश्राम का उपयोग करना।
 यदि बाधा <math>x_S\in\{0,1\}</math> द्वारा प्रतिस्थापित किया जाता है <math>x_S \geq 0</math> सभी के लिए {{var|S}} में <math>\mathcal{S}</math> पूर्णांक रैखिक कार्यक्रम में #पूर्णांक रैखिक कार्यक्रम सूत्रीकरण दिखाया गया है, तो यह एक (गैर-पूर्णांक) रैखिक कार्यक्रम बन जाता है {{var|L}}. एल्गोरिथ्म को इस प्रकार वर्णित किया जा सकता है:
 # एक इष्टतम समाधान खोजें {{var|O}} कार्यक्रम के लिए {{var|L}} रैखिक कार्यक्रमों को हल करने के लिए कुछ बहुपद-समय पद्धति का उपयोग करना।
-# सभी सेट चुनें {{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> इसका मूल्य कम से कम 1/ है{{var|f}} समाधान में {{var|O}}.<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 |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>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>ई.जी.
-== भारित सेट कवर ==
+== भारित सम्मुच्चय आवरक ==
 {{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 19:56, 3 July 2023

Contents

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

हिटिंग सम्मुच्चय फॉर्मूलेशन

लालची एल्गोरिदम

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

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

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

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 19:56, 3 July 2023

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

हिटिंग सम्मुच्चय फॉर्मूलेशन

लालची एल्गोरिदम

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

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

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

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

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories