सम्मुच्चय आवरक समस्या

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

तत्वों का एक सेट (गणित) दिया गया है {1, 2, …, 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}})$, और कार्य एक ऐसा सेट कवर ढूंढना है जो सबसे कम सेट का उपयोग करता हो।

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

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

न्यूनतम सेट कवर समस्या को निम्नलिखित पूर्णांक रैखिक कार्यक्रम (ILP) के रूप में तैयार किया जा सकता है।

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$ ब्रह्मांड का आकार है)। भारित सेट कवर में, सेट को वजन दिया जाता है। सेट के वजन को निरूपित करें $s\in {\mathcal {S}}$ द्वारा $w_{s}$. फिर भारित सेट कवर का वर्णन करने वाला पूर्णांक रैखिक कार्यक्रम ऊपर दिए गए के समान है, सिवाय इसके कि न्यूनतम करने का उद्देश्य कार्य है $\sum _{s\in {\mathcal {S}}}w_{s}x_{s}$.

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

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

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

सेट कवरिंग के बहुपद समय सन्निकटन के लिए एक लालची एल्गोरिदम है जो एक नियम के अनुसार सेट चुनता है: प्रत्येक चरण में, वह सेट चुनें जिसमें सबसे बड़ी संख्या में शामिल न हों। सेट को प्राथमिकता देने के लिए बकेट कतार का उपयोग करके, इस पद्धति को इनपुट सेट के आकार के योग में समय रैखिक में लागू किया जा सकता है। यह का अनुमानित अनुपात प्राप्त करता है $H(s)$, कहाँ $s$ कवर किए जाने वाले सेट का आकार है. दूसरे शब्दों में, यह एक ऐसा आवरण ढूंढ लेता है जो हो सकता है $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$.

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)$.

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

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

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

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

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

कब $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)$-कारक सन्निकटन. गैर भारित सेट कवर को भारित केस के अनुसार अनुकूलित किया जा सकता है।

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

• हिटिंग सेट, सेट कवर का समतुल्य पुनर्रचना है।
• वर्टेक्स कवर समस्या हिटिंग सेट का एक विशेष मामला है।
• एज कवर समस्या सेट कवर का एक विशेष मामला है।
• ज्यामितीय सेट कवर समस्या सेट कवर का एक विशेष मामला है जब ब्रह्मांड बिंदुओं का एक सेट होता है $\mathbb {R} ^{d}$ और सेट ब्रह्मांड और ज्यामितीय आकृतियों (जैसे, डिस्क, आयत) के प्रतिच्छेदन से प्रेरित होते हैं।
• पैकिंग सेट करें
• अधिकतम कवरेज समस्या अधिक से अधिक तत्वों को कवर करने के लिए अधिकतम k सेट चुनना है।
• डोमिनेटिंग सेट एक ग्राफ़ में शीर्षों के एक सेट (डोमिनेटिंग सेट) को इस प्रकार चुनने की समस्या है कि अन्य सभी शीर्ष सेट पर दबदबा में कम से कम एक शीर्ष के निकट हों। डोमिनेटिंग सेट समस्या को सेट कवर से कमी के माध्यम से एनपी पूर्ण दिखाया गया था।
• सटीक कवर समस्या एक ऐसे सेट कवर को चुनना है जिसमें एक से अधिक कवरिंग सेट में कोई तत्व शामिल न हो।
• लाल नीला सेट कवर।
• सेट-कवर अपहरण.

संदर्भ

• 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)

बाहरी संबंध

• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
• A compendium of NP optimization problems - Minimum Set Cover