आच्छादित समस्याएं

साहचर्य और कंप्यूटर विज्ञान में, समस्याओं को आच्छादित करना कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित सांयोगिक संरचना दूसरे को 'आच्छादित' करता है, या ऐसा करने के लिए संरचना कितनी बड़ी होनी चाहिए। संवरण समस्याएं न्यूनीकरण (गणित) की समस्याएँ हैं और सामान्य रूप से पूर्णांक रैखिक प्रोग्राम हैं, जिनकी दोहरी समस्याओं को पैकिंग समस्याएं कहा जाता है।

संवरण (कवरिंग) समस्याओं का सबसे प्रमुख उदाहरण समुच्चय आच्छादित समस्या है, जो अघाती समुच्चय समस्या के बराबर है, और इसके विशेष स्थिति मे, शीर्ष आच्छादित समस्या और कोर आच्छादित समस्या है।

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

रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक प्रोग्राम को एक संवरण समस्या के रूप में विचार कर सकते हैं यदि प्रतिबंध आव्यूह (गणित), उद्देश्य फलन, और दक्षिणावर्ती पक्ष की ओर गुणांक गैर-ऋणात्मक हैं। अधिक परिशुद्ध रूप से, निम्नलिखित सामान्य पूर्णांक रैखिक प्रोग्राम पर विचार करें:

न्यूनतम	$\sum _{i=1}^{n}c_{i}x_{i}$
यदि	$\sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ for }}j=1,\dots ,m$
	$x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ for }}i=1,\dots ,n$.

इस तरह के एक पूर्णांक रैखिक प्रोग्राम को संवरण समस्या कहा जाता है यदि $a_{ji},b_{j},c_{i}\geq 0$ सभी के लिए $i=1,\dots ,n$ और $j=1,\dots ,m$.

अंतर्ज्ञान: मान लीजिए $n$ प्रकार की वस्तु है और प्रत्येक प्रकार की वस्तु $i$ की संबद्ध कीमत $c_{i}$ होती है। जो संख्या $x_{i}$ इंगित करता है कि $i$ प्रकार की कितनी वस्तुएं हैं जो हम ख़रीदते हैं। यदि व्यवरोध $A\mathbf {x} \geq \mathbf {b}$ संतुष्ट हैं, तो यह कहा जाता है कि $\mathbf {x}$ एक संवरण है आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं। अंत में, उपरोक्त पूर्णांक रैखिक प्रोग्राम का इष्टतम समाधान न्यूनतम मूल्य को आच्छादित करता है।

समस्याओं को आच्छादित करने के प्रकार

ग्राफ सिद्धांत, कम्प्यूटेशनल ज्यामिति में विभिन्न प्रकार की संवरण समस्याएं हैं; और अधिक श्रेणी संवरण समस्याएं देखें।। समस्या के अन्य प्रसंभाव्यता संबंधित संस्करण मिल सकते हैं।

उदाहरण के लिए पेट्री मूल्य के लिए, संवरण समस्या को प्रश्न के रूप में परिभाषित किया गया है यदि किसी दिए गए अंकन, मूल्य का एक क्रम सम्मिलित है, जैसे कि कुछ बृहत् (या बराबर) अंकन तक पहुंचा जा सकता है। यहां बृहत का तात्पर्य है कि सभी घटक कम से कम दिए गए अंकन के जितने बड़े हैं और कम से कम एक उपयुक्त रूप से बड़ा है।

इंद्रधनुष का आच्छादित और अंतर्द्वंदव (कॉन्फ्लिक्ट)-मुक्त आच्छादित

कुछ संवरण समस्याओं में, संवरण को कुछ अतिरिक्त आवश्यकताओं को पूरा करना चाहिए। विशेष रूप से, इंद्रधनुष संवरण समस्या में, प्रत्येक मूल वस्तु का एक रंग होता है, और यह आवश्यक है कि संवरण में प्रत्येक रंग की एक (या अधिक से अधिक एक) वस्तु सम्मिलित हो। इंद्रधनुष संवरण का अध्ययन किया गया था उदाहरण अंतराल (गणित) द्वारा बिंदुओं को आच्छादित करने के लिए:

• वास्तविक रेखा पर n रंगीन अंतरालों का एक समुच्चय J है, और वास्तविक रेखा पर बिंदुओं का एक समुच्चय है।
• J के एक उपसमुच्चय Q को इंद्रधनुषी समुच्चय कहा जाता है यदि इसमें प्रत्येक रंग का अधिक से अधिक एक अंतराल हो।
• अंतराल J के एक उप-समुच्चय को P का संवरण कहा जाता है यदि P का प्रत्येक बिंदु Q के कम से कम एक अंतराल में समाहित है।
• इंद्रधनुष संवरण समस्या इंद्रधनुष समुच्चय Q को खोजने की समस्या है जो कि P का संवरण है।

समस्या एनपी-कठिन (रैखिक एसएटी से कमी से) है।

अधिक सामान्य धारणा ' अंतर्द्वंदव-मुक्त संवरण' है। इस समस्या में:

• m वस्तु का एक समुच्चय O है, और O पर एक अंतर्द्वंदव -आरेख G_O है।
• O के एक उपसमुच्चय Q को अंतर्द्वंदव-मुक्त कहा जाता है यदि यह G_O में एक स्वतंत्र समुच्चय है, अर्थात, Q में कोई भी दो वस्तुएँ G_O में एक कोर से जुड़ी नहीं हैं।
• एक इंद्रधनुष समुच्चय विशेष स्थितियों में एक अंतर्द्वंदव-मुक्त समुच्चय है जिसमें G_Oअलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है।

अंतर्द्वंदव-मुक्त समुच्चय संवरण O का एक अंतर्द्वंदव-मुक्त उपसमुच्चय खोजने की समस्या है जो कि P. बनिक, पानोलन, रमन, सहलोत और सौरभ का एक संवरण है गणितीय प्रमाण निम्नलिखित विशेष स्थितियों के लिए जिसमें अंतर्द्वंदव-आरेख ने अरबोरिसिटी को सीमित किया है:

• यदि ज्यामितीय आच्छादित समस्या निश्चित-पैरामीटर आसानी से प्रभावित होने वाला (एफपीटी) होता है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी है।
• यदि ज्यामितीय आच्छादित समस्या एक r-सन्निकटन एल्गोरिथ्म को स्वीकार करती है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी समय में समान सन्निकटन एल्गोरिथ्म को स्वीकार करती है।