समुच्चय संवेष्टन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[साहचर्य]] में [[सबसेट]] संवेष्टन एक | [[कम्प्यूटेशनल जटिलता सिद्धांत]] और [[साहचर्य]] में [[सबसेट|उपसमुच्चय]] संवेष्टन एक पारम्परिक NP-पूर्ण समस्या है, और कार्प की 21 NP-पूर्ण समस्याओं में से एक थी। मान लीजिए कि किसी के पास एक परिमित समुच्चय ''S'' है और ''S'' के उपसमुच्चय की एक सूची है। फिर, '''सम्मुच्चय संवेष्टन''' समस्या पूछती है कि सूची में कुछ k उपसमुच्चय जोड़ीदार [[अलग सेट|अलग सम्मुच्चय]] हैं (दूसरे शब्दों में, उनमें से कोई भी तत्व साझा नहीं करता है)। | ||
अधिक औपचारिक रूप से, एक | अधिक औपचारिक रूप से, एक समष्टि <math>\mathcal{U}</math> और उपसमुच्चय <math>\mathcal{U}</math> का एक वर्ग <math>\mathcal{S}</math> दिया गया है, संवेष्टन एक उपवर्ग <math>\mathcal{C}\subseteq\mathcal{S}</math> है, सम्मुच्चय के ऐसे कि <math>\mathcal{C}</math> में सभी सम्मुच्चय जोड़े में अलग हैं। संवेष्टन का आकार <math>|\mathcal{C}|</math> है। सम्मुच्चय संवेष्टन [[निर्णय समस्या]] में, निविष्ट एक जोड़ी <math>(\mathcal{U},\mathcal{S})</math> और एक पूर्णांक <math>k</math> है; सवाल यह है कि क्या आकार का एक सम्मुच्चय संवेष्टन <math>k</math> या अधिक है। सम्मुच्चय संवेष्टन [[अनुकूलन समस्या]] में, निविष्ट एक जोड़ी <math>(\mathcal{U},\mathcal{S})</math> है, और कार्य एक सम्मुच्चय संवेष्टन ढूंढना है जो सबसे अधिक सम्मुच्चय का उपयोग करता है। | ||
आकार का एक सम्मुच्चय संवेष्टन | |||
समस्या स्पष्ट रूप से | समस्या स्पष्ट रूप से NP में है, दिए गए t उपसमुच्चय के बाद से, हम आसानी से सत्यापित कर सकते हैं कि वे बहुपद समय में जोड़ीदार हैं। | ||
समस्या की अनुकूलन समस्या, 'अधिकतम सम्मुच्चय संवेष्टन', सूची में जोड़ीदार असंयुक्त सम्मुच्चय की अधिकतम संख्या के लिए पूछती है। यह एक अधिकतमकरण समस्या है जिसे संवेष्टन समस्याओं के वर्ग से संबंधित एक [[पूर्णांक रैखिक कार्यक्रम]] के रूप में स्वाभाविक रूप से तैयार किया जा सकता है। | समस्या की अनुकूलन समस्या, 'अधिकतम सम्मुच्चय संवेष्टन', सूची में जोड़ीदार असंयुक्त सम्मुच्चय की अधिकतम संख्या के लिए पूछती है। यह एक अधिकतमकरण समस्या है जिसे संवेष्टन समस्याओं के वर्ग से संबंधित एक [[पूर्णांक रैखिक कार्यक्रम]] के रूप में स्वाभाविक रूप से तैयार किया जा सकता है। | ||
| Line 19: | Line 17: | ||
| (उपसमुच्चय की कुल संख्या को अधिकतम करें) | | (उपसमुच्चय की कुल संख्या को अधिकतम करें) | ||
|- | |- | ||
| | | अधीन | ||
| <math>\sum_{S\colon e \in S} x_S \leqslant 1 </math> | | <math>\sum_{S\colon e \in S} x_S \leqslant 1 </math> | ||
| for all <math>e\in \mathcal U</math> | | for all <math>e\in \mathcal U</math> | ||
| Line 33: | Line 31: | ||
== जटिलता == | == जटिलता == | ||
सम्मुच्चय संवेष्टन समस्या न केवल | सम्मुच्चय संवेष्टन समस्या न केवल NP-पूर्ण है, बल्कि इसका अनुकूलन संस्करण (सामान्य अधिकतम सम्मुच्चय संवेष्टन समस्या) को अधिकतम क्लिक समस्या के रूप में अनुमानित करना कठिन सिद्ध हुआ है; विशेष रूप से, इसे किसी स्थिर कारक के भीतर अनुमानित नहीं किया जा सकता है।<ref>{{citation | ||
| last1 = Hazan | first1 = Elad | | last1 = Hazan | first1 = Elad | ||
| last2 = Safra | first2 = Shmuel | | last2 = Safra | first2 = Shmuel | ||
| Line 46: | Line 44: | ||
| year = 2006| citeseerx = 10.1.1.352.5754 | | year = 2006| citeseerx = 10.1.1.352.5754 | ||
| s2cid = 1858087 | | s2cid = 1858087 | ||
}}. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within <math>O(n^{1-\epsilon})</math> unless NP ⊂ ZPP."</ref> सबसे | }}. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within <math>O(n^{1-\epsilon})</math> unless NP ⊂ ZPP."</ref> सबसे अच्छी ज्ञात कलन विधि इसके एक कारक <math>O(\sqrt{|U|})</math> के भीतर इसका अनुमान लगाती है। <ref>{{cite conference | ||
| last1 = Halldórsson | first1 = Magnus M. | | last1 = Halldórsson | first1 = Magnus M. | ||
| last2 = Kratochvíl | first2 = Jan | | last2 = Kratochvíl | first2 = Jan | ||
| Line 57: | Line 55: | ||
| pages = 176–185 | | pages = 176–185 | ||
| year = 1998 | | year = 1998 | ||
}}</ref> | }}</ref> भारित परिवर्त्य को भी अनुमानित किया जा सकता है।<ref>{{cite conference | ||
| last = Halldórsson | first = Magnus M. | | last = Halldórsson | first = Magnus M. | ||
| year = 1999 | | year = 1999 | ||
| Line 69: | Line 67: | ||
== | == संकुल आकार के साथ संवेष्टन सम्मुच्चय == | ||
समस्या का एक संस्करण है जो अधिक | समस्या का एक संस्करण है जो अधिक सुविधाजनक है। किसी भी धनात्मक पूर्णांक k≥3 को देखते हुए, ''''k-सम्मुच्चय संवेष्टन समस्या'''<nowiki/>' सम्मुच्चय संवेष्टन का एक प्रकार है जिसमें प्रत्येक सम्मुच्चय में अधिकतम k तत्व होते हैं। | ||
जब k = 1, समस्या तुच्छ है। जब k = 2, समस्या एक [[अधिकतम कार्डिनैलिटी मिलान]] खोजने के बराबर होती है, जिसे बहुपद समय में हल किया जा सकता है। | जब k = 1, समस्या तुच्छ है। जब k = 2, समस्या एक [[अधिकतम कार्डिनैलिटी मिलान|अधिकतम गणनांक मिलान]] खोजने के बराबर होती है, जिसे बहुपद समय में हल किया जा सकता है। | ||
किसी भी k≥3 के लिए, समस्या | किसी भी k≥3 के लिए, समस्या NP-कठोर है, क्योंकि यह [[3-आयामी मिलान]] से अधिक सामान्य है। हालाँकि, [[निरंतर-कारक सन्निकटन एल्गोरिदम|निरंतर-कारक सन्निकटन कलन विधि]] हैं: | ||
* साइगन<ref>{{Cite journal |last=Cygan |first=Marek |date=October 2013 |title=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |url=https://ieeexplore.ieee.org/document/6686187 |journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> एक | * साइगन ने <ref>{{Cite journal |last=Cygan |first=Marek |date=October 2013 |title=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |url=https://ieeexplore.ieee.org/document/6686187 |journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> एक कलन विधि प्रस्तुत करी, जो किसी भी ε>0 के लिए, एक (k+1+ε)/3 सन्निकटन प्राप्त करता है। कार्यावधि सम्मुच्चय और तत्वों की संख्या में बहुपद है, लेकिन 1/ε में दोगुना-घातीय है। | ||
* फ्यूरर और यू<ref>{{Cite journal |last1=Fürer |first1=Martin |last2=Yu |first2=Huiwen |date=2014 |editor-last=Fouilhoux |editor-first=Pierre |editor2-last=Gouveia |editor2-first=Luis Eduardo Neves |editor3-last=Mahjoub |editor3-first=A. Ridha |editor4-last=Paschos |editor4-first=Vangelis T. |title=स्थानीय सुधारों द्वारा $$k$$-सेट पैकिंग समस्या का अनुमान लगाना|url=https://link.springer.com/chapter/10.1007/978-3-319-09174-7_35 |journal=Combinatorial Optimization |series=Lecture Notes in Computer Science |volume=8596 |language=en |location=Cham |publisher=Springer International Publishing |pages=408–420 |doi=10.1007/978-3-319-09174-7_35 |isbn=978-3-319-09174-7|s2cid=15815885 }}</ref> एक | * फ्यूरर और यू ने <ref>{{Cite journal |last1=Fürer |first1=Martin |last2=Yu |first2=Huiwen |date=2014 |editor-last=Fouilhoux |editor-first=Pierre |editor2-last=Gouveia |editor2-first=Luis Eduardo Neves |editor3-last=Mahjoub |editor3-first=A. Ridha |editor4-last=Paschos |editor4-first=Vangelis T. |title=स्थानीय सुधारों द्वारा $$k$$-सेट पैकिंग समस्या का अनुमान लगाना|url=https://link.springer.com/chapter/10.1007/978-3-319-09174-7_35 |journal=Combinatorial Optimization |series=Lecture Notes in Computer Science |volume=8596 |language=en |location=Cham |publisher=Springer International Publishing |pages=408–420 |doi=10.1007/978-3-319-09174-7_35 |isbn=978-3-319-09174-7|s2cid=15815885 }}</ref> एक कलन विधि करी जो 1/ε में कार्यावधि एकधा-घातांकी के साथ समान सन्निकटन प्राप्त करता है। | ||
== एक सीमित | == एक सीमित घात के साथ संवेष्टन सम्मुच्चय == | ||
एक अन्य अधिक सुगम संस्करण में, यदि उपसमुच्चय के k से अधिक में कोई तत्व नहीं होता है, तो उत्तर को k के कारक के भीतर अनुमानित किया जा सकता है। भारित संस्करण के लिए भी यही सच है। | एक अन्य अधिक सुगम संस्करण में, यदि उपसमुच्चय के k से अधिक में कोई तत्व नहीं होता है, तो उत्तर को k के कारक के भीतर अनुमानित किया जा सकता है। भारित संस्करण के लिए भी यही सच है। | ||
| Line 87: | Line 85: | ||
[[हाइपरग्राफ मिलान]] सम्मुच्चय संवेष्टन के समतुल्य है: सम्मुच्चय हाइपरएज के अनुरूप होते हैं। | [[हाइपरग्राफ मिलान]] सम्मुच्चय संवेष्टन के समतुल्य है: सम्मुच्चय हाइपरएज के अनुरूप होते हैं। | ||
स्वतंत्र सम्मुच्चय ( | स्वतंत्र सम्मुच्चय (आरेख सिद्धांत) समस्या भी सम्मुच्चय संवेष्टन के समतुल्य है - उनके बीच एक-से-एक बहुपद-समय की कमी है: | ||
* | * संग्रह पर एक सम्मुच्चय संवेष्टन समस्या <math>\mathcal{S}</math> को देखते हुए, एक लेखाचित्र बनाएं जहां प्रत्येक सम्मुच्चय <math>S \in \mathcal{S}</math> के लिए एक शिखर <math>v_S</math> है, और बीच में एक किनारा <math>v_S</math> और <math>v_T</math> आईएफएफ <math>S \cap T \neq \varnothing</math> है। उत्पन्न किए गए आरेख में कोने का हर स्वतंत्र सम्मुच्चय एक सम्मुच्चय संवेष्टन <math>\mathcal{S}</math> से मेल खाता है। | ||
* एक | * एक लेखाचित्र पर एक स्वतंत्र कोणबिंदु सम्मुच्चय समस्या <math>G(V,E)</math> दी गई है, सम्मुच्चय का एक संग्रह बनाएँ जहाँ प्रत्येक शीर्ष <math>v</math> के लिए <math>v</math> से सटे सभी किनारों से युक्त एक सम्मुच्चय <math>S_v</math> है। उत्पन्न किए गए संग्रह में प्रत्येक सम्मुच्चय संवेष्टन एक स्वतंत्र कोणबिंदु सम्मुच्चय <math>G(V,E)</math> से मेल खाती है। | ||
यह एक द्विदिश पीटीएएस कमी भी है, और यह दर्शाता है कि दो समस्याओं का अनुमान लगाना समान रूप से कठिन है। | यह एक द्विदिश पीटीएएस कमी भी है, और यह दर्शाता है कि दो समस्याओं का अनुमान लगाना समान रूप से कठिन है। | ||
विशेष | विशेष स्तिथि में जब प्रत्येक सम्मुच्चय में अधिकांश k तत्व (k-सम्मुच्चय संवेष्टन समस्या) होते हैं, तो प्रतिच्छेदन लेखाचित्र (k+1) क्लॉ-मुक्त होता है। ऐसा इसलिए है, क्योंकि यदि कोई समुच्चय कुछ k+1 समुच्चयों को काटता है, तो इनमें से कम से कम दो समुच्चय प्रतिच्छेद करते हैं, इसलिए (k+1)-क्लॉ नहीं हो सकता। तो क्लॉ मुक्त रेखांकन में अधिकतम स्वतंत्र सम्मुच्चय <ref>{{Cite journal |last=Neuwohner |first=Meike |date=2021-06-07 |title=डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम|arxiv=2106.03545 }}</ref> अधिकतम k-सम्मुच्चय संवेष्टन के सामान्यीकरण के रूप में देखा जा सकता है। | ||
=== विशेष | === विशेष स्तिथि === | ||
मिलान ( | मिलान (लेखाचित्र सिद्धांत) सम्मुच्चय संवेष्टन की एक विशेष स्तिथि है जिसमें सभी सम्मुच्चयों का आकार 2 होता है (सम्मुच्चय किनारों के अनुरूप होते हैं)। इस विशेष स्तिथि में, बहुपद समय में अधिकतम आकार का मिलान पाया जा सकता है। | ||
3-आयामी मिलान एक विशेष | 3-आयामी मिलान एक विशेष स्तिथि है जिसमें सभी सम्मुच्चयों का आकार 3 होता है, और इसके अतिरिक्त, तत्वों को 3 रंगों में विभाजित किया जाता है और प्रत्येक सम्मुच्चय में प्रत्येक रंग का एक तत्व होता है। यह विशेष स्तिथि अभी भी NP-ठोस है, हालांकि इसमें सामान्य स्तिथि की तुलना में बेहतर स्थिर-कारक सन्निकटन कलन विधि हैं। | ||
=== अन्य संबंधित समस्याएं === | === अन्य संबंधित समस्याएं === | ||
[[ कवर समस्या सेट करें | | [[ कवर समस्या सेट करें |सम्मुच्चय आवरण समस्या]] में, हमें ब्रह्मांड <math>\mathcal{U}</math> के उपसमुच्चय का एक वर्ग <math>\mathcal{S}</math> दिया गया है, और लक्ष्य यह निर्धारित करना है कि क्या हम k सम्मुच्चय चुन सकते हैं जिसमें एक साथ सभी तत्व <math>\mathcal{U}</math> सम्मिलित हैं। ये सम्मुच्चय अतिछादित हो सकते हैं। अनुकूलन संस्करण ऐसे सम्मुच्चयों की न्यूनतम संख्या पाता है। अधिकतम सम्मुच्चय संवेष्टन में हर संभव तत्व को सम्मिलित करने की आवश्यकता नहीं है। | ||
यथार्थ आवरण समस्या में, <math>\mathcal{U}</math> का हर तत्व ठीक एक उपसमुच्चय में समाहित होना चाहिए। इस तरह के एक यथार्थ आवरण को खोजना एक NP-पूर्ण समस्या है, विशेष स्तिथि में भी जिसमें सभी सम्मुच्चयों का आकार 3 है (इस विशेष स्तिथि को 'यथार्थ 3 आवरण' या 'X3C' कहा जाता है)। हालाँकि, यदि हम S के प्रत्येक तत्व के लिए एक [[सिंगलटन सेट|एकल सम्मुच्चय]] बनाते हैं और इन्हें सूची में जोड़ते हैं, तो परिणामी समस्या सम्मुच्चय संवेष्टन जितनी आसान होती है। | |||
कार्प ने मूल रूप से '[[क्लिक समस्या]]' से कमी के माध्यम से सम्मुच्चय संवेष्टन | कार्प ने मूल रूप से '[[क्लिक समस्या]]' से कमी के माध्यम से सम्मुच्चय संवेष्टन NP-पूर्ण दिखाया। | ||
{{See also|हाइपरग्राफ में संकुलन }} | {{See also|हाइपरग्राफ में संकुलन }} | ||
| Line 129: | Line 127: | ||
*[https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf Optimizing Three-Dimensional Bin Packing] | *[https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf Optimizing Three-Dimensional Bin Packing] | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category: | [[Category:CS1 English-language sources (en)]] | ||
[[Category:CS1 errors]] | |||
[[Category:Collapse templates]] | |||
[[Category: | |||
[[Category:Created On 06/05/2023]] | [[Category:Created On 06/05/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:एनपी-पूर्ण समस्याएं]] | |||
[[Category:साहचर्य]] | |||
Latest revision as of 12:49, 7 November 2023
कम्प्यूटेशनल जटिलता सिद्धांत और साहचर्य में उपसमुच्चय संवेष्टन एक पारम्परिक NP-पूर्ण समस्या है, और कार्प की 21 NP-पूर्ण समस्याओं में से एक थी। मान लीजिए कि किसी के पास एक परिमित समुच्चय S है और S के उपसमुच्चय की एक सूची है। फिर, सम्मुच्चय संवेष्टन समस्या पूछती है कि सूची में कुछ k उपसमुच्चय जोड़ीदार अलग सम्मुच्चय हैं (दूसरे शब्दों में, उनमें से कोई भी तत्व साझा नहीं करता है)।
अधिक औपचारिक रूप से, एक समष्टि और उपसमुच्चय का एक वर्ग दिया गया है, संवेष्टन एक उपवर्ग है, सम्मुच्चय के ऐसे कि में सभी सम्मुच्चय जोड़े में अलग हैं। संवेष्टन का आकार है। सम्मुच्चय संवेष्टन निर्णय समस्या में, निविष्ट एक जोड़ी और एक पूर्णांक है; सवाल यह है कि क्या आकार का एक सम्मुच्चय संवेष्टन या अधिक है। सम्मुच्चय संवेष्टन अनुकूलन समस्या में, निविष्ट एक जोड़ी है, और कार्य एक सम्मुच्चय संवेष्टन ढूंढना है जो सबसे अधिक सम्मुच्चय का उपयोग करता है।
समस्या स्पष्ट रूप से NP में है, दिए गए t उपसमुच्चय के बाद से, हम आसानी से सत्यापित कर सकते हैं कि वे बहुपद समय में जोड़ीदार हैं।
समस्या की अनुकूलन समस्या, 'अधिकतम सम्मुच्चय संवेष्टन', सूची में जोड़ीदार असंयुक्त सम्मुच्चय की अधिकतम संख्या के लिए पूछती है। यह एक अधिकतमकरण समस्या है जिसे संवेष्टन समस्याओं के वर्ग से संबंधित एक पूर्णांक रैखिक कार्यक्रम के रूप में स्वाभाविक रूप से तैयार किया जा सकता है।
पूर्णांक रैखिक कार्यक्रम सूत्रीकरण
अधिकतम सम्मुच्चय संवेष्टन समस्या को निम्न पूर्णांक रैखिक कार्यक्रम के रूप में तैयार किया जा सकता है।
| अधिकतम | (उपसमुच्चय की कुल संख्या को अधिकतम करें) | ||
| अधीन | for all | (चयनित सम्मुच्चयों को जोड़ो में अलग करना होगा) | |
| for all . | (हर सम्मुच्चय या तो सम्मुच्चय संवेष्टन में है या नहीं) |
जटिलता
सम्मुच्चय संवेष्टन समस्या न केवल NP-पूर्ण है, बल्कि इसका अनुकूलन संस्करण (सामान्य अधिकतम सम्मुच्चय संवेष्टन समस्या) को अधिकतम क्लिक समस्या के रूप में अनुमानित करना कठिन सिद्ध हुआ है; विशेष रूप से, इसे किसी स्थिर कारक के भीतर अनुमानित नहीं किया जा सकता है।[1] सबसे अच्छी ज्ञात कलन विधि इसके एक कारक के भीतर इसका अनुमान लगाती है। [2] भारित परिवर्त्य को भी अनुमानित किया जा सकता है।[3]
संकुल आकार के साथ संवेष्टन सम्मुच्चय
समस्या का एक संस्करण है जो अधिक सुविधाजनक है। किसी भी धनात्मक पूर्णांक k≥3 को देखते हुए, 'k-सम्मुच्चय संवेष्टन समस्या' सम्मुच्चय संवेष्टन का एक प्रकार है जिसमें प्रत्येक सम्मुच्चय में अधिकतम k तत्व होते हैं।
जब k = 1, समस्या तुच्छ है। जब k = 2, समस्या एक अधिकतम गणनांक मिलान खोजने के बराबर होती है, जिसे बहुपद समय में हल किया जा सकता है।
किसी भी k≥3 के लिए, समस्या NP-कठोर है, क्योंकि यह 3-आयामी मिलान से अधिक सामान्य है। हालाँकि, निरंतर-कारक सन्निकटन कलन विधि हैं:
- साइगन ने [4] एक कलन विधि प्रस्तुत करी, जो किसी भी ε>0 के लिए, एक (k+1+ε)/3 सन्निकटन प्राप्त करता है। कार्यावधि सम्मुच्चय और तत्वों की संख्या में बहुपद है, लेकिन 1/ε में दोगुना-घातीय है।
- फ्यूरर और यू ने [5] एक कलन विधि करी जो 1/ε में कार्यावधि एकधा-घातांकी के साथ समान सन्निकटन प्राप्त करता है।
एक सीमित घात के साथ संवेष्टन सम्मुच्चय
एक अन्य अधिक सुगम संस्करण में, यदि उपसमुच्चय के k से अधिक में कोई तत्व नहीं होता है, तो उत्तर को k के कारक के भीतर अनुमानित किया जा सकता है। भारित संस्करण के लिए भी यही सच है।
संबंधित समस्याएं
समतुल्य समस्याएं
हाइपरग्राफ मिलान सम्मुच्चय संवेष्टन के समतुल्य है: सम्मुच्चय हाइपरएज के अनुरूप होते हैं।
स्वतंत्र सम्मुच्चय (आरेख सिद्धांत) समस्या भी सम्मुच्चय संवेष्टन के समतुल्य है - उनके बीच एक-से-एक बहुपद-समय की कमी है:
- संग्रह पर एक सम्मुच्चय संवेष्टन समस्या को देखते हुए, एक लेखाचित्र बनाएं जहां प्रत्येक सम्मुच्चय के लिए एक शिखर है, और बीच में एक किनारा और आईएफएफ है। उत्पन्न किए गए आरेख में कोने का हर स्वतंत्र सम्मुच्चय एक सम्मुच्चय संवेष्टन से मेल खाता है।
- एक लेखाचित्र पर एक स्वतंत्र कोणबिंदु सम्मुच्चय समस्या दी गई है, सम्मुच्चय का एक संग्रह बनाएँ जहाँ प्रत्येक शीर्ष के लिए से सटे सभी किनारों से युक्त एक सम्मुच्चय है। उत्पन्न किए गए संग्रह में प्रत्येक सम्मुच्चय संवेष्टन एक स्वतंत्र कोणबिंदु सम्मुच्चय से मेल खाती है।
यह एक द्विदिश पीटीएएस कमी भी है, और यह दर्शाता है कि दो समस्याओं का अनुमान लगाना समान रूप से कठिन है।
विशेष स्तिथि में जब प्रत्येक सम्मुच्चय में अधिकांश k तत्व (k-सम्मुच्चय संवेष्टन समस्या) होते हैं, तो प्रतिच्छेदन लेखाचित्र (k+1) क्लॉ-मुक्त होता है। ऐसा इसलिए है, क्योंकि यदि कोई समुच्चय कुछ k+1 समुच्चयों को काटता है, तो इनमें से कम से कम दो समुच्चय प्रतिच्छेद करते हैं, इसलिए (k+1)-क्लॉ नहीं हो सकता। तो क्लॉ मुक्त रेखांकन में अधिकतम स्वतंत्र सम्मुच्चय [6] अधिकतम k-सम्मुच्चय संवेष्टन के सामान्यीकरण के रूप में देखा जा सकता है।
विशेष स्तिथि
मिलान (लेखाचित्र सिद्धांत) सम्मुच्चय संवेष्टन की एक विशेष स्तिथि है जिसमें सभी सम्मुच्चयों का आकार 2 होता है (सम्मुच्चय किनारों के अनुरूप होते हैं)। इस विशेष स्तिथि में, बहुपद समय में अधिकतम आकार का मिलान पाया जा सकता है।
3-आयामी मिलान एक विशेष स्तिथि है जिसमें सभी सम्मुच्चयों का आकार 3 होता है, और इसके अतिरिक्त, तत्वों को 3 रंगों में विभाजित किया जाता है और प्रत्येक सम्मुच्चय में प्रत्येक रंग का एक तत्व होता है। यह विशेष स्तिथि अभी भी NP-ठोस है, हालांकि इसमें सामान्य स्तिथि की तुलना में बेहतर स्थिर-कारक सन्निकटन कलन विधि हैं।
अन्य संबंधित समस्याएं
सम्मुच्चय आवरण समस्या में, हमें ब्रह्मांड के उपसमुच्चय का एक वर्ग दिया गया है, और लक्ष्य यह निर्धारित करना है कि क्या हम k सम्मुच्चय चुन सकते हैं जिसमें एक साथ सभी तत्व सम्मिलित हैं। ये सम्मुच्चय अतिछादित हो सकते हैं। अनुकूलन संस्करण ऐसे सम्मुच्चयों की न्यूनतम संख्या पाता है। अधिकतम सम्मुच्चय संवेष्टन में हर संभव तत्व को सम्मिलित करने की आवश्यकता नहीं है।
यथार्थ आवरण समस्या में, का हर तत्व ठीक एक उपसमुच्चय में समाहित होना चाहिए। इस तरह के एक यथार्थ आवरण को खोजना एक NP-पूर्ण समस्या है, विशेष स्तिथि में भी जिसमें सभी सम्मुच्चयों का आकार 3 है (इस विशेष स्तिथि को 'यथार्थ 3 आवरण' या 'X3C' कहा जाता है)। हालाँकि, यदि हम S के प्रत्येक तत्व के लिए एक एकल सम्मुच्चय बनाते हैं और इन्हें सूची में जोड़ते हैं, तो परिणामी समस्या सम्मुच्चय संवेष्टन जितनी आसान होती है।
कार्प ने मूल रूप से 'क्लिक समस्या' से कमी के माध्यम से सम्मुच्चय संवेष्टन NP-पूर्ण दिखाया।
टिप्पणियाँ
- ↑ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "On the complexity of approximating k-set packing", Computational Complexity, 15 (1): 20–39, CiteSeerX 10.1.1.352.5754, doi:10.1007/s00037-006-0205-6, MR 2226068, S2CID 1858087. See in particular p. 21: "Maximum clique (and therefore also maximum independent set and maximum set packing) cannot be approximated to within unless NP ⊂ ZPP."
- ↑ Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Independent sets with domination constraints. 25th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 1443. Springer-Verlag. pp. 176–185.
- ↑ Halldórsson, Magnus M. (1999). Approximations of weighted independent set and hereditary subset problems. 5th Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 1627. Springer-Verlag. pp. 261–270.
- ↑ Cygan, Marek (October 2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 509–518. arXiv:1304.1424. doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646.
- ↑ Fürer, Martin; Yu, Huiwen (2014). Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (eds.). "स्थानीय सुधारों द्वारा $$k$$-सेट पैकिंग समस्या का अनुमान लगाना". Combinatorial Optimization. Lecture Notes in Computer Science (in English). Cham: Springer International Publishing. 8596: 408–420. doi:10.1007/978-3-319-09174-7_35. ISBN 978-3-319-09174-7. S2CID 15815885.
- ↑ Neuwohner, Meike (2021-06-07). "डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम". arXiv:2106.03545.
{{cite journal}}: Cite journal requires|journal=(help)
संदर्भ
- 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
