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

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

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

समस्या स्पष्ट रूप से NP में है, दिए गए t उपसमुच्चय के बाद से, हम आसानी से सत्यापित कर सकते हैं कि वे बहुपद समय में जोड़ीदार हैं।

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

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

अधिकतम सम्मुच्चय संवेष्टन समस्या को निम्न पूर्णांक रैखिक कार्यक्रम के रूप में तैयार किया जा सकता है।

अधिकतम	$\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$ के लिए $v$ से सटे सभी किनारों से युक्त एक सम्मुच्चय $S_{v}$ है। उत्पन्न किए गए संग्रह में प्रत्येक सम्मुच्चय संवेष्टन एक स्वतंत्र कोणबिंदु सम्मुच्चय $G(V,E)$ से मेल खाती है।

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

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

विशेष स्तिथि

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

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

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

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

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

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

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