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

सम्मुच्चय आवरक समस्या साहचर्य, कंप्यूटर विज्ञान, संचालन अनुसंधान और संगणनात्मक जटिलता सिद्धांत में एक पारम्परिक प्रश्न है। यह कार्प की 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}})$ है, और कार्य एक ऐसा सम्मुच्चय आवरक ढूंढना है जो सबसे कम सम्मुच्चय का उपयोग करता हो।

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

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

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

न्यूनतमीकरण	$\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$ समष्टि का आकार है) देती है।

भारित सम्मुच्चय आवरक में, सम्मुच्चय को भार दिया जाता है। सम्मुच्चय के भार $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