पैकिंग सेट करें

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

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

समस्या स्पष्ट रूप से एनपी (जटिलता) में दी गई है $t$ उपसमुच्चय, हम आसानी से सत्यापित कर सकते हैं कि वे P (जटिलता) में जोड़ीदार रूप से असंयुक्त हैं।

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

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

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

maximize	$\sum _{S\in {\mathcal {S}}}x_{S}$		(maximize the total number of subsets)
subject to	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	for all $e\in {\mathcal {U}}$	(selected sets have to be pairwise disjoint)
	$x_{S}\in \{0,1\}$	for all $S\in {\mathcal {S}}$.	(every set is either in the set packing or not)

जटिलता

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

एक बंधे हुए आकार के साथ पैकिंग सेट

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

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

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

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

एक सीमित डिग्री के साथ पैकिंग सेट

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

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

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

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

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

• एक संग्रह पर एक सेट पैकिंग समस्या को देखते हुए ${\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}}$, और लक्ष्य यह निर्धारित करना है कि क्या हम उन सेटों को चुन सकते हैं जिनमें एक साथ सभी तत्व शामिल हैं ${\mathcal {U}}$. ये सेट ओवरलैप हो सकते हैं। अनुकूलन संस्करण ऐसे सेटों की न्यूनतम संख्या पाता है। अधिकतम सेट पैकिंग में हर संभव तत्व को शामिल करने की आवश्यकता नहीं है।

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

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

See also: Packing in a hypergraph

संदर्भ

• 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