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

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

कवरिंग समस्याओं के सबसे प्रमुख उदाहरण हैं सेट कवर समस्या, जो हिटिंग सेट के समतुल्य है, और इसके विशेष मामले, वर्टेक्स कवर समस्या और एज कवर समस्या।

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

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

minimize	$\sum _{i=1}^{n}c_{i}x_{i}$
subject to	$\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 का कवरिंग है।

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

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

• एम ऑब्जेक्ट्स का एक सेट ओ है, और एक संघर्ष-ग्राफ जी है_Oओ पर।
• O के एक सबसेट Q को संघर्ष-मुक्त कहा जाता है यदि यह G में एक स्वतंत्र सेट (ग्राफ सिद्धांत) है_O, अर्थात, Q में कोई भी दो वस्तुएँ G में किसी किनारे से जुड़ी नहीं हैं_O.
• एक इंद्रधनुष सेट विशेष मामले में एक संघर्ष-मुक्त सेट है जिसमें G_Oअलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है।

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

• यदि ज्यामितीय कवर समस्या फिक्स्ड-पैरामीटर एल्गोरिथ्म | फिक्स्ड-पैरामीटर ट्रैक्टेबल (FPT) है, तो संघर्ष-मुक्त ज्यामितीय कवर समस्या FPT है।
• यदि ज्यामितीय आवरण समस्या एक आर-सन्निकटन एल्गोरिथ्म को स्वीकार करती है, तो संघर्ष-मुक्त ज्यामितीय आवरण समस्या FPT समय में समान सन्निकटन एल्गोरिथ्म को स्वीकार करती है।