समुच्चय संवेष्टन

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

अधिक औपचारिक रूप से, एक ब्रह्मांड दिया ${\mathcal {U}}$ और एक परिवार ${\mathcal {S}}$ के सबसेट का ${\mathcal {U}}$, एक संवेष्टन एक उपपरिवार है ${\mathcal {C}}\subseteq {\mathcal {S}}$ सम्मुच्चय के ऐसे कि सभी सम्मुच्चय हो जाते हैं ${\mathcal {C}}$ जोड़ीदार असंयुक्त हैं। संवेष्टन का आकार है $|{\mathcal {C}}|$. सम्मुच्चय संवेष्टन निर्णय समस्या में, इनपुट एक जोड़ी है $({\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}\leqslant 1$	for all $e\in {\mathcal {U}}$	(चयनित सम्मुच्चयों को जोड़ो में अलग करना होगा)
	$x_{S}\in \{0,1\}$	for all $S\in {\mathcal {S}}$.	(हर सम्मुच्चय या तो सम्मुच्चय संवेष्टन में है या नहीं)

जटिलता

सम्मुच्चय संवेष्टन समस्या न केवल एनपी-पूर्ण है, बल्कि इसका अनुकूलन संस्करण (सामान्य अधिकतम सम्मुच्चय संवेष्टन समस्या) को अधिकतम क्लिक समस्या के रूप में अनुमानित करना मुश्किल साबित हुआ है; विशेष रूप से, इसे किसी स्थिर कारक के भीतर अनुमानित नहीं किया जा सकता है। सबसे अच्छा ज्ञात एल्गोरिथम इसके एक कारक के भीतर इसका अनुमान लगाता है $O({\sqrt {|U|}})$. वेटेड वेरिएंट को भी अनुमानित किया जा सकता है।

एक बंधे हुए आकार के साथ संवेष्टन सम्मुच्चय

समस्या का एक संस्करण है जो अधिक ट्रैक्टेबल है। किसी भी धनात्मक पूर्णांक k≥3 को देखते हुए, 'k-सम्मुच्चय संवेष्टन समस्या' सम्मुच्चय संवेष्टन का एक प्रकार है जिसमें प्रत्येक सम्मुच्चय में अधिकतम k तत्व होते हैं।

जब k = 1, समस्या तुच्छ है। जब k = 2, समस्या एक अधिकतम कार्डिनैलिटी मिलान खोजने के बराबर होती है, जिसे बहुपद समय में हल किया जा सकता है।

किसी भी k≥3 के लिए, समस्या एनपी-हार्ड है, क्योंकि यह 3-आयामी मिलान से अधिक सामान्य है। हालाँकि, निरंतर-कारक सन्निकटन एल्गोरिदम हैं:

• साइगन एक एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, एक (k+1+ε)/3 सन्निकटन प्राप्त करता है। रन-टाइम सम्मुच्चय और तत्वों की संख्या में बहुपद है, लेकिन 1/ε में दोगुना-घातीय है।
• फ्यूरर और यू एक एल्गोरिदम प्रस्तुत किया जो समान सन्निकटन प्राप्त करता है, लेकिन 1/ε में रन-टाइम सिंगल-एक्सपोनेंशियल के साथ।

एक सीमित डिग्री के साथ संवेष्टन सम्मुच्चय

एक अन्य अधिक सुगम संस्करण में, यदि उपसमुच्चय के k से अधिक में कोई तत्व नहीं होता है, तो उत्तर को k के कारक के भीतर अनुमानित किया जा सकता है। भारित संस्करण के लिए भी यही सच है।

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

समतुल्य समस्याएं

हाइपरग्राफ मिलान सम्मुच्चय संवेष्टन के समतुल्य है: सम्मुच्चय हाइपरएज के अनुरूप होते हैं।

स्वतंत्र सम्मुच्चय (ग्राफ़ सिद्धांत) समस्या भी सम्मुच्चय संवेष्टन के समतुल्य है - उनके बीच एक-से-एक बहुपद-समय की कमी है:

• एक संग्रह पर एक सम्मुच्चय संवेष्टन समस्या को देखते हुए ${\mathcal {S}}$, एक ग्राफ बनाएं जहां प्रत्येक सम्मुच्चय के लिए $S\in {\mathcal {S}}$ एक शिखर है $v_{S}$, और बीच में एक किनारा है $v_{S}$ और $v_{T}$ आईएफएफ $S\cap T\neq \varnothing$. जनरेट किए गए ग्राफ़ में कोने का हर स्वतंत्र सम्मुच्चय एक सम्मुच्चय संवेष्टन से मेल खाता है ${\mathcal {S}}$.
• एक ग्राफ पर एक स्वतंत्र वर्टेक्स सम्मुच्चय समस्या दी गई है $G(V,E)$, सम्मुच्चय का एक संग्रह बनाएँ जहाँ प्रत्येक शीर्ष के लिए $v$ एक सम्मुच्चय है $S_{v}$ सभी किनारों से सटे हुए $v$. जेनरेट किए गए संग्रह में प्रत्येक सम्मुच्चय संवेष्टन एक स्वतंत्र वर्टेक्स सम्मुच्चय से मेल खाती है $G(V,E)$.

यह एक द्विदिश पीटीएएस कमी भी है, और यह दर्शाता है कि दो समस्याओं का अनुमान लगाना समान रूप से कठिन है।

विशेष मामले में जब प्रत्येक सम्मुच्चय में अधिकांश k तत्व (k-सम्मुच्चय संवेष्टन समस्या) होते हैं, तो प्रतिच्छेदन ग्राफ (k+1)पंजा मुक्त ग्राफ|क्लॉ-फ़्री होता है। ऐसा इसलिए है, क्योंकि यदि कोई समुच्चय कुछ k+1 समुच्चयों को काटता है, तो इनमें से कम से कम दो समुच्चय प्रतिच्छेद करते हैं, इसलिए (k+1)-पंजा नहीं हो सकता। तो पंजा मुक्त रेखांकन में अधिकतम स्वतंत्र सम्मुच्चय अधिकतम के-सम्मुच्चय संवेष्टन के सामान्यीकरण के रूप में देखा जा सकता है।

विशेष मामले

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

3-आयामी मिलान एक विशेष मामला है जिसमें सभी सेटों का आकार 3 होता है, और इसके अलावा, तत्वों को 3 रंगों में विभाजित किया जाता है और प्रत्येक सम्मुच्चय में प्रत्येक रंग का एक तत्व होता है। यह विशेष मामला अभी भी एनपी-हार्ड है, हालांकि इसमें सामान्य मामले की तुलना में बेहतर स्थिर-कारक सन्निकटन एल्गोरिदम हैं।

अन्य संबंधित समस्याएं

कवर समस्या सम्मुच्चय करें में हमें एक परिवार दिया जाता है ${\mathcal {S}}$ एक ब्रह्मांड के सबसेट की ${\mathcal {U}}$, और लक्ष्य यह निर्धारित करना है कि क्या हम k सम्मुच्चय चुन सकते हैं जिसमें एक साथ सभी तत्व शामिल हैं ${\mathcal {U}}$. ये सम्मुच्चय ओवरलैप हो सकते हैं। अनुकूलन संस्करण ऐसे सेटों की न्यूनतम संख्या पाता है। अधिकतम सम्मुच्चय संवेष्टन में हर संभव तत्व को शामिल करने की आवश्यकता नहीं है।

सटीक कवर समस्या में, का हर तत्व ${\mathcal {U}}$ ठीक एक उपसमुच्चय में समाहित होना चाहिए। इस तरह के एक सटीक कवर को खोजना एक एनपी-पूर्ण समस्या है, विशेष मामले में भी जिसमें सभी सेटों का आकार 3 है (इस विशेष मामले को 'सटीक 3 कवर' या 'X3C' कहा जाता है)। हालाँकि, यदि हम S के प्रत्येक तत्व के लिए एक सिंगलटन सम्मुच्चय बनाते हैं और इन्हें सूची में जोड़ते हैं, तो परिणामी समस्या सम्मुच्चय संवेष्टन जितनी आसान होती है।

कार्प ने मूल रूप से 'क्लिक समस्या' से कमी के माध्यम से सम्मुच्चय संवेष्टन एनपी-पूर्ण दिखाया।

See also: हाइपरग्राफ में संकुलन

संदर्भ

• Maximum Set Packing, Viggo Kann.
• "set packing". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
• Steven S. Skiena. "Set Packing". The Algorithm Design Manual.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems. Last modified March 20, 2000.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A3.1: SP3, pg.221.
• Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 978-3-540-65367-7.

बाहरी संबंध

• [1]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, ISBN 0-13-215509-5.
• Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
• Solving packaging problem in PHP
• Optimizing Three-Dimensional Bin Packing