आच्छादित समस्याएं: Difference between revisions

Revision as of 20:58, 15 May 2023

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

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

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

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

न्यूनतम	$\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}$ एक संवरण है आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं। अंत में, उपरोक्त पूर्णांक रैखिक प्रोग्राम का इष्टतम समाधान न्यूनतम मूल्य को आच्छादित करता है।

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

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

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

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

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

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

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

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

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

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

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

संदर्भ

↑ Vazirani, Vijay V. (2001). सन्निकटन एल्गोरिदम. Springer-Verlag. ISBN 3-540-65367-8.^: 112
↑ Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link)
↑ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "रंगीन बिंदुओं का चयन करना और उन्हें ढंकना". Discrete Applied Mathematics (in English). 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.
↑ Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम". Computational Geometry (in English). 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.
↑ Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता". Algorithmica (in English). 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.

[1] Vazirani, Vijay V. (2001). सन्निकटन एल्गोरिदम. Springer-Verlag. ISBN 3-540-65367-8.^: 112

[2] Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022). "The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches" (PDF). European Journal of Operational Research, 299 (2022), 945–959}.{{cite web}}: CS1 maint: multiple names: authors list (link)

[3] Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "रंगीन बिंदुओं का चयन करना और उन्हें ढंकना". Discrete Applied Mathematics (in English). 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.

[4] Banik, Aritra; Sahlot, Vibha; Saurabh, Saket (2020-08-01). "ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम". Computational Geometry (in English). 89: 101591. doi:10.1016/j.comgeo.2019.101591. ISSN 0925-7721. S2CID 209959954.

[5] Banik, Aritra; Panolan, Fahad; Raman, Venkatesh; Sahlot, Vibha; Saurabh, Saket (2020-01-01). "विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता". Algorithmica (in English). 82 (1): 1–19. doi:10.1007/s00453-019-00600-w. ISSN 1432-0541. S2CID 254027914.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{Short description|Type of computational problem}}
-[[साहचर्य]] और [[ कंप्यूटर विज्ञान ]] में, समस्याओं को कवर करना कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित कॉम्बिनेटरियल स्ट्रक्चर दूसरे को 'कवर' करता है, या संरचना को ऐसा करने के लिए कितना बड़ा होना चाहिए। कवरिंग समस्याएं [[अनुकूलन (गणित)]] हैं और आमतौर पर [[पूर्णांक रैखिक कार्यक्रम]] हैं, जिनकी [[दोहरी समस्या]]ओं को पैकिंग समस्याएं कहा जाता है।
+[[साहचर्य]] और [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, '''समस्याओं को आच्छादित करना''' कम्प्यूटेशनल समस्याएं हैं जो पूछती हैं कि क्या एक निश्चित सांयोगिक संरचना दूसरे को 'आच्छादित' करता है, या ऐसा करने के लिए संरचना कितनी बड़ी होनी चाहिए। संवरण समस्याएं [[अनुकूलन (गणित)|न्यूनीकरण (गणित)]] की समस्याएँ हैं और सामान्य रूप से [[पूर्णांक रैखिक कार्यक्रम|पूर्णांक रैखिक प्रोग्राम]] हैं, जिनकी [[दोहरी समस्या]]ओं को पैकिंग समस्याएं कहा जाता है।
-कवरिंग समस्याओं के सबसे प्रमुख उदाहरण हैं सेट कवर समस्या, जो [[हिटिंग सेट]] के समतुल्य है, और इसके विशेष मामले, [[वर्टेक्स कवर समस्या]] और एज कवर समस्या।
+संवरण (कवरिंग) समस्याओं का सबसे प्रमुख उदाहरण समुच्चय आच्छादित समस्या है, जो अघाती समुच्चय समस्या के बराबर है, और इसके विशेष स्थिति मे, शीर्ष आच्छादित समस्या और कोर आच्छादित समस्या है।
 {{Covering-Packing_Problem_Pairs}}
 == सामान्य [[रैखिक प्रोग्रामिंग]] सूत्रीकरण ==
-रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक कार्यक्रम को एक कवरिंग समस्या के रूप में सोच सकते हैं यदि बाधा [[मैट्रिक्स (गणित)]], उद्देश्य समारोह, और दाएं हाथ की तरफ गुणांक गैर-नकारात्मक हैं।<ref>{{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=सन्निकटन एल्गोरिदम| year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 }}{{rp|112}}
+रैखिक प्रोग्रामिंग के संदर्भ में, किसी भी रैखिक प्रोग्राम को एक संवरण समस्या के रूप में विचार कर सकते हैं यदि प्रतिबंध [[मैट्रिक्स (गणित)|आव्यूह (गणित)]], उद्देश्य फलन, और दक्षिणावर्ती पक्ष की ओर गुणांक गैर-ऋणात्मक हैं।<ref>{{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=सन्निकटन एल्गोरिदम| year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 }}{{rp|112}}
-</ref> अधिक सटीक रूप से, निम्नलिखित सामान्य [[पूर्णांक रैखिक कार्यक्रम]] पर विचार करें:
+</ref> अधिक परिशुद्ध रूप से, निम्नलिखित सामान्य [[पूर्णांक रैखिक कार्यक्रम|पूर्णांक रैखिक प्रोग्राम]] पर विचार करें:
 {|
-| minimize
+| न्यूनतम
 | <math>\sum_{i=1}^n c_i x_i</math>
 |-
-| subject to
+| यदि
 | <math> \sum_{i=1}^n a_{ji} x_i \geq b_j \text{ for }j=1,\dots,m</math>
 |-
@@ Line 19: / Line 19: @@
 | <math>x_i \in \left\{0, 1, 2, \ldots\right\}\text{ for }i=1,\dots,n</math>.
 |}
-इस तरह के एक पूर्णांक रैखिक कार्यक्रम को कवरिंग समस्या कहा जाता है यदि <math>a_{ji}, b_j, c_i \geq 0</math> सभी के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math>.
+इस तरह के एक पूर्णांक रैखिक प्रोग्राम को संवरण समस्या कहा जाता है यदि <math>a_{ji}, b_j, c_i \geq 0</math> सभी के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math>.
-अंतर्ज्ञान: मान लीजिए <math>n</math> वस्तु के प्रकार और प्रकार की प्रत्येक वस्तु <math>i</math> की संबद्ध लागत है <math>c_i</math>. जो नंबर <math>x_i</math> इंगित करता है कि प्रकार की कितनी वस्तुएं हैं <math>i</math> हम ख़रीदते हैं। यदि विवशताएँ <math>A\mathbf{x}\geq \mathbf{b}</math> संतुष्ट हैं, ऐसा कहा जाता है<math>\mathbf{x}</math> एक आच्छादन है (आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं)। अंत में, उपरोक्त पूर्णांक रैखिक कार्यक्रम का इष्टतम समाधान न्यूनतम लागत का कवर है।
+'''अंतर्ज्ञान''': मान लीजिए <math>n</math> प्रकार की वस्तु है और प्रत्येक प्रकार की वस्तु <math>i</math> की संबद्ध कीमत <math>c_i</math> होती है। जो संख्या <math>x_i</math> इंगित करता है कि <math>i</math> प्रकार की कितनी वस्तुएं हैं जो हम ख़रीदते हैं। यदि व्यवरोध <math>A\mathbf{x}\geq \mathbf{b}</math> संतुष्ट हैं, तो यह कहा जाता है कि <math>\mathbf{x}</math> एक संवरण है आच्छादित संरचनाएं मिश्रित संदर्भ पर निर्भर करती हैं। अंत में, उपरोक्त पूर्णांक रैखिक प्रोग्राम का इष्टतम समाधान न्यूनतम मूल्य को आच्छादित करता है।
-==समस्याओं को कवर करने के प्रकार==
+==समस्याओं को आच्छादित करने के प्रकार==
-[[ ग्राफ सिद्धांत ]], [[ कम्प्यूटेशनल ज्यामिति ]] और बहुत कुछ में विभिन्न प्रकार की कवरिंग समस्याएं हैं; देखें :श्रेणी:समस्याओं को कवर करना। समस्या के अन्य स्टोकास्टिक संबंधित संस्करण मिल सकते हैं। <ref>{{cite web|author =    Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022)|title = The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches |url =  http://www.eng.tau.ac.il/~bengal/STCP.pdf|publisher = European Journal of Operational Research, 299 (2022), 945–959} }}</ref>
+[[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]], [[ कम्प्यूटेशनल ज्यामिति |कम्प्यूटेशनल ज्यामिति]] में विभिन्न प्रकार की संवरण समस्याएं हैं; और अधिक श्रेणी संवरण समस्याएं देखें।। समस्या के अन्य प्रसंभाव्यता संबंधित संस्करण मिल सकते हैं। <ref>{{cite web|author =    Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022)|title = The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches |url =  http://www.eng.tau.ac.il/~bengal/STCP.pdf|publisher = European Journal of Operational Research, 299 (2022), 945–959} }}</ref>
-[[पेट्री नेट]] के लिए, उदाहरण के लिए, कवरिंग प्रॉब्लम को प्रश्न के रूप में परिभाषित किया गया है यदि किसी दिए गए मार्किंग के लिए, नेट का एक रन मौजूद है, जैसे कि कुछ बड़े (या बराबर) मार्किंग तक पहुंचा जा सकता है। यहां बड़े का मतलब है कि सभी घटक कम से कम दिए गए अंकन के जितने बड़े हैं और कम से कम एक उचित रूप से बड़ा है।
-== {{Anchor|rainbow}}इंद्रधनुष का आवरण और संघर्ष-मुक्त आवरण ==
+उदाहरण के लिए [[पेट्री नेट|पेट्री]] मूल्य के लिए, संवरण समस्या को प्रश्न के रूप में परिभाषित किया गया है यदि किसी दिए गए अंकन, मूल्य का एक क्रम सम्मिलित है, जैसे कि कुछ बृहत् (या बराबर) अंकन तक पहुंचा जा सकता है। यहां बृहत का तात्पर्य है कि सभी घटक कम से कम दिए गए अंकन के जितने बड़े हैं और कम से कम एक उपयुक्त रूप से बड़ा है।
-कुछ कवरिंग समस्याओं में, कवरिंग को कुछ अतिरिक्त आवश्यकताओं को पूरा करना चाहिए। विशेष रूप से, इंद्रधनुष कवरिंग समस्या में, प्रत्येक मूल वस्तु का एक रंग होता है, और यह आवश्यक है कि कवरिंग में प्रत्येक रंग की एक (या अधिक से अधिक एक) वस्तु शामिल हो। इंद्रधनुष कवरिंग का अध्ययन किया गया था उदा। [[अंतराल (गणित)]] द्वारा बिंदुओं को कवर करने के लिए:<ref>{{Cite journal|last1=Arkin|first1=Esther M.|last2=Banik|first2=Aritra|last3=Carmi|first3=Paz|last4=Citovsky|first4=Gui|last5=Katz|first5=Matthew J.|last6=Mitchell|first6=Joseph S. B.|last7=Simakov|first7=Marina|date=2018-12-11|title=रंगीन बिंदुओं का चयन करना और उन्हें ढंकना|journal=Discrete Applied Mathematics|language=en|volume=250|pages=75–86|doi=10.1016/j.dam.2018.05.011|issn=0166-218X|doi-access=free}}</ref>
+== इंद्रधनुष का आच्छादित और अंतर्द्वंदव (कॉन्फ्लिक्ट)-मुक्त आच्छादित ==
+कुछ संवरण समस्याओं में, संवरण को कुछ अतिरिक्त आवश्यकताओं को पूरा करना चाहिए। विशेष रूप से, इंद्रधनुष संवरण समस्या में, प्रत्येक मूल वस्तु का एक रंग होता है, और यह आवश्यक है कि संवरण में प्रत्येक रंग की एक (या अधिक से अधिक एक) वस्तु सम्मिलित हो। इंद्रधनुष संवरण का अध्ययन किया गया था उदाहरण [[अंतराल (गणित)]] द्वारा बिंदुओं को आच्छादित करने के लिए:<ref>{{Cite journal|last1=Arkin|first1=Esther M.|last2=Banik|first2=Aritra|last3=Carmi|first3=Paz|last4=Citovsky|first4=Gui|last5=Katz|first5=Matthew J.|last6=Mitchell|first6=Joseph S. B.|last7=Simakov|first7=Marina|date=2018-12-11|title=रंगीन बिंदुओं का चयन करना और उन्हें ढंकना|journal=Discrete Applied Mathematics|language=en|volume=250|pages=75–86|doi=10.1016/j.dam.2018.05.011|issn=0166-218X|doi-access=free}}</ref>
 * [[वास्तविक रेखा]] पर n रंगीन अंतरालों का एक समुच्चय J है, और वास्तविक रेखा पर बिंदुओं का एक समुच्चय है।
 * J के एक उपसमुच्चय Q को इंद्रधनुषी समुच्चय कहा जाता है यदि इसमें प्रत्येक रंग का अधिक से अधिक एक अंतराल हो।
-* अंतराल J के एक [[सबसेट]] को P का आवरण कहा जाता है यदि P का प्रत्येक बिंदु Q के कम से कम एक अंतराल में समाहित है।
+* अंतराल J के एक [[सबसेट|उप-समुच्चय]] को P का संवरण कहा जाता है यदि P का प्रत्येक बिंदु Q के कम से कम एक अंतराल में समाहित है।
-* रेनबो कवरिंग प्रॉब्लम इंद्रधनुष सेट Q को खोजने की समस्या है जो कि P का कवरिंग है।
+* इंद्रधनुष संवरण समस्या इंद्रधनुष समुच्चय Q को खोजने की समस्या है जो कि P का संवरण है।
-समस्या [[एनपी-कठोरता]] है | एनपी-हार्ड (रैखिक एसएटी से कमी करके)।
+समस्या एनपी-कठिन (रैखिक एसएटी से कमी से) है।
-एक अधिक सामान्य धारणा 'संघर्ष-मुक्त आवरण' है।<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Sahlot|first2=Vibha|last3=Saurabh|first3=Saket|date=2020-08-01|title=ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम|url=http://www.sciencedirect.com/science/article/pii/S0925772119301324|journal=Computational Geometry|language=en|volume=89|pages=101591|doi=10.1016/j.comgeo.2019.101591|s2cid=209959954 |issn=0925-7721}}</ref> इस समस्या में:
+अधिक सामान्य धारणा ' अंतर्द्वंदव-मुक्त संवरण' है।<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Sahlot|first2=Vibha|last3=Saurabh|first3=Saket|date=2020-08-01|title=ज्यामितीय संघर्ष मुक्त कवरिंग समस्याओं के लिए सन्निकटन एल्गोरिदम|url=http://www.sciencedirect.com/science/article/pii/S0925772119301324|journal=Computational Geometry|language=en|volume=89|pages=101591|doi=10.1016/j.comgeo.2019.101591|s2cid=209959954 |issn=0925-7721}}</ref> इस समस्या में:
-* एम ऑब्जेक्ट्स का एक सेट ओ है, और एक संघर्ष-ग्राफ जी है<sub>O</sub>ओ पर।
+* m वस्तु का एक समुच्चय O है, और O पर एक अंतर्द्वंदव -आरेख ''G<sub>O</sub>'' है।
-* O के एक सबसेट Q को संघर्ष-मुक्त कहा जाता है यदि यह G में एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)]] है<sub>O</sub>, अर्थात, Q में कोई भी दो वस्तुएँ G में किसी किनारे से जुड़ी नहीं हैं<sub>O</sub>.
+* O के एक उपसमुच्चय Q को अंतर्द्वंदव-मुक्त कहा जाता है यदि यह ''G<sub>O</sub>'' में एक स्वतंत्र समुच्चय है, अर्थात, Q में कोई भी दो वस्तुएँ ''G<sub>O</sub>'' में एक कोर से जुड़ी नहीं हैं।
-* एक इंद्रधनुष सेट विशेष मामले में एक संघर्ष-मुक्त सेट है जिसमें G<sub>O</sub>अलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है।
+* एक इंद्रधनुष समुच्चय विशेष स्थितियों में एक ''अंतर्द्वंदव''-मुक्त समुच्चय है जिसमें G<sub>O</sub>अलग-अलग समूहों से बना है, जहां प्रत्येक समूह एक रंग का प्रतिनिधित्व करता है।
-संघर्ष-मुक्त सेट कवर O का एक संघर्ष-मुक्त उपसमुच्चय खोजने की समस्या है जो कि P. बनिक, पानोलन, रमन, सहलोत और सौरभ का एक आवरण है<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|s2cid=254027914 |issn=1432-0541}}</ref> गणितीय सबूत निम्नलिखित विशेष मामले के लिए जिसमें संघर्ष-ग्राफ ने [[वृक्षारोपण]] को सीमित किया है:
+अंतर्द्वंदव-मुक्त समुच्चय संवरण O का एक अंतर्द्वंदव-मुक्त उपसमुच्चय खोजने की समस्या है जो कि P. बनिक, पानोलन, रमन, सहलोत और सौरभ का एक संवरण है<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=विरोधाभासी होने वाली ज्यामितीय आवरण समस्याओं की पैरामिट्रीकृत जटिलता|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|s2cid=254027914 |issn=1432-0541}}</ref> गणितीय प्रमाण निम्नलिखित विशेष स्थितियों के लिए जिसमें अंतर्द्वंदव-आरेख ने [[वृक्षारोपण|अरबोरिसिटी]] को सीमित किया है:
-* यदि ज्यामितीय कवर समस्या [[ फिक्स्ड-पैरामीटर एल्गोरिथ्म ]] | फिक्स्ड-पैरामीटर ट्रैक्टेबल (FPT) है, तो संघर्ष-मुक्त ज्यामितीय कवर समस्या FPT है।
+* यदि ज्यामितीय आच्छादित समस्या निश्चित-पैरामीटर आसानी से प्रभावित होने वाला (एफपीटी) होता है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी है।
-* यदि ज्यामितीय आवरण समस्या एक आर-सन्निकटन एल्गोरिथ्म को स्वीकार करती है, तो संघर्ष-मुक्त ज्यामितीय आवरण समस्या FPT समय में समान सन्निकटन एल्गोरिथ्म को स्वीकार करती है।
+* यदि ज्यामितीय आच्छादित समस्या एक r-सन्निकटन एल्गोरिथ्म को स्वीकार करती है, तो अंतर्द्वंदव-मुक्त ज्यामितीय आच्छादित समस्या एफपीटी समय में समान सन्निकटन एल्गोरिथ्म को स्वीकार करती है।
 ==संदर्भ==

Anonymous

Search

आच्छादित समस्याएं: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:58, 15 May 2023

Contents

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

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आच्छादित समस्याएं: Difference between revisions

Revision as of 20:58, 15 May 2023

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

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories