Matroid-constrained number partitioning
मेट्रॉइड-सीमित संख्या विभाजन बहु-मार्ग संख्या विभाजन समस्या का एक प्रकार है, जिसमें विभाजन में सबसेट एक मेट्रॉइड के स्वतंत्र सेट होने चाहिए। इस समस्या के लिए इनपुट वस्तुओं का एक सेट S, एक सकारात्मक पूर्णांक m, और एक ही सेट S पर कुछ m मैट्रोइड है। लक्ष्य S को m सबसेट में विभाजित करना है, जैसे कि प्रत्येक सबसेट i मैट्रोइड i में एक स्वतंत्र सेट है। इस बाधा के अधीन, कुछ वस्तुनिष्ठ कार्य को न्यूनतम किया जाना चाहिए, उदाहरण के लिए, एक उपसमुच्चय में सबसे बड़ी राशि वस्तु के आकार को न्यूनतम करना। एक अधिक सामान्य संस्करण में, प्रत्येक एम मेट्रॉइड का एक वजन कार्य होता है, जो ग्राउंड-सेट के प्रत्येक तत्व को एक वजन निर्धारित करता है। विभिन्न वस्तुनिष्ठ कार्यों पर विचार किया गया है। तीन प्रचालक अधिकतम, न्यूनतम, योग में से प्रत्येक के लिए, कोई भी इस प्रचालक का उपयोग प्रत्येक उपसमुच्चय में वस्तुओं के भार पर और स्वयं उपसमुच्चय पर कर सकता है। कुल मिलाकर, 9 संभावित वस्तुनिष्ठ कार्य हैं, जिनमें से प्रत्येक को अधिकतम या न्यूनतम किया जा सकता है। विशेष मामले मैट्रायड-सीमित विभाजन समस्याओं के कुछ महत्वपूर्ण विशेष मामले हैंः (अधिकतम, योग) उद्देश्य सभी सबसेट पर सबसे अधिक है, सबसेट में कुल वजन का। जब वस्तुएँ कार्य का प्रतिनिधित्व करती हैं और वजन उनकी लंबाई का प्रतिनिधित्व करते हैं, तो यह उद्देश्य केवल अनुसूची का निर्माण है। इसलिए, इस उद्देश्य को कम करना मैट्रायड बाधाओं के तहत मेकस्पैन को कम करने के बराबर है। इस संदर्भ में अधिकतम (न्यूनतम, योग) के दोहरे लक्ष्य का भी अध्ययन किया गया है। विशेष मामला जिसमें मेट्रॉइड मुक्त मेट्रॉइड होते हैं (कोई बाधा नहीं) और एम वजन-कार्य समान होते हैं, समान-मशीन शेड्यूलिंग से मेल खाते हैं, जिसे मल्टीवे नंबर विभाजन के रूप में भी जाना जाता है। मुक्त मेट्रॉइड और विभिन्न वजन-कार्यों का मामला असंबंधित-मशीनों के समय निर्धारण से मेल खाता है। समान मेट्रॉइड का विशेष मामला सबसेट पर कार्डिनलिटी बाधाओं से मेल खाता है। विभाजन मेट्रॉइड का अधिक सामान्य मामला वर्गीकृत कार्डिनलिटी बाधाओं से मेल खाता है। संतुलित संख्या विभाजन पर पृष्ठ में इन समस्याओं का वर्णन किया गया है। (योग, योग) उद्देश्य सभी उपसमुच्चय में सभी वस्तुओं के भार का योग है, जहां प्रत्येक उपसमुच्चय में भार की गणना मैट्रायड i के भार-फलन द्वारा की जाती है। इस उद्देश्य को कम करने के लिए भारित मैट्रायड प्रतिच्छेदन समस्या को कम किया जा सकता है-एक अधिकतम वजन उपसमुच्चय का पता लगाना जो दो दिए गए मैट्रायड में एक साथ स्वतंत्र है। यह समस्या बहुपद समय में हल की जा सकती है। (अधिकतम, अधिकतम) उद्देश्य सभी उपसमुच्चय में अधिकतम वजन है, जहां प्रत्येक उपसमुच्चय i में भार की गणना मैट्रायड i के भार-फलन द्वारा की जाती है। ग्राफिक मेट्रॉइड के साथ इस उद्देश्य को कम करने का उपयोग न्यूनतम अड़चन फैलाने वाली वृक्ष समस्या को हल करने के लिए किया जा सकता है। (योग, न्यूनतम) उद्देश्य सभी उपसमुच्चय में न्यूनतम भार का योग है। इस उद्देश्य को अधिकतम करने के लिए, k समान ग्राफिकल मैट्रोइड के साथ, पेड़ विभाजन समस्या को फैलाने वाली अधिकतम कुल क्षमता को हल करने के लिए उपयोग किया जा सकता है। (योग, अधिकतम) उद्देश्य सभी उपसमुच्चय में अधिकतम भार का योग है। यह उद्देश्य शेड्यूलिंग के लिए आवश्यक कुल मेमोरी का प्रतिनिधित्व कर सकता है, जब प्रत्येक मैट्रायड i मशीन i में व्यवहार्य आवंटन का प्रतिनिधित्व करता है। सामान्य मैट्रायड बाधाओं पर सबसे पहले बर्कार्ड और याओ द्वारा विचार किया गया था। उन्होंने दिखाया कि मैट्रोइड्स के एक उपवर्ग के लिए एक लालची एल्गोरिथ्म द्वारा बहुपद समय में न्यूनतम (योग, अधिकतम) किया जा सकता है, जिसमें विभाजन मैट्रोइड्स शामिल हैं। ह्वांग और रोथब्लम ने एक वैकल्पिक पर्याप्त शर्त प्रस्तुत की। वू और याओ ने सामान्य मैट्रायड बाधाओं के साथ न्यूनतम (अधिकतम, योग) के लिए एक सन्निकटन एल्गोरिथ्म प्रस्तुत किया। अब्बासी, मिरोकनी और ठाकुर मैट्रायड बाधाओं के तहत विविधता अधिकतमकरण की समस्या के लिए एक सन्निकटन एल्गोरिदम प्रस्तुत करते हैं। कावासे, किमुरा, माकिनो और सुमिता बताते हैं कि अधिकतमकरण की समस्याओं को न्यूनतम समस्या तक कम किया जा सकता है। फिर, वे सात न्यूनतम समस्याओं का विश्लेषण करते हैंः न्यूनतम (योग, अधिकतम): समस्या प्रबल रूप से एन. पी.-कठोर है, तब भी जब मैट्रोइड और भार समान हों। समान मैट्रोइड और वजन के लिए एक पी. टी. ए. एस. है। सामान्य मेट्रॉइड और भार के लिए, किसी भी ε> 0 के लिए एक εm-एप्रॉक्सिमेशन एल्गोरिथ्म है। यह कारक ओ (लॉग एम) के साथ अनुमानित करने के लिए एनपी-कठिन है। न्यूनतम (न्यूनतम, न्यूनतम), (अधिकतम, अधिकतम), (न्यूनतम, अधिकतम) और (न्यूनतम, योग): बहुपद-समय एल्गोरिदम हैं। वे समस्याओं को मैट्रायड विभाजन समस्या की व्यवहार्यता समस्या तक कम कर देते हैं। न्यूनतम (अधिकतम, न्यूनतम) और (योग, न्यूनतम): समान मैट्रोइड और भार के लिए बहुपद-समय एल्गोरिदम हैं। सामान्य मामले में, यह दृढ़ता से एन. पी.-कठिन है, यहां तक कि अनुमानित भी। अन्य दो समस्याओं का पिछले कार्यों में विश्लेषण किया गया थाः न्यूनतम (अधिकतम, योग) को दृढ़ता से एनपी-हार्ड (3-विभाजन एक विशेष मामला है) के रूप में जाना जाता है, और न्यूनतम (योग, योग) को भारित मैट्रायड प्रतिच्छेदन में कम किया जा सकता है, जो बहुपद है। संबंधित समस्याएं मैट्रायड विभाजन एक अलग समस्या है, जिसमें भागों की संख्या m तय नहीं है। एक एकल मैट्रायड है, और इसका लक्ष्य इसके तत्वों को स्वतंत्र सेटों की सबसे छोटी संख्या में विभाजित करना है। संदर्भ मैट्रायड सिद्धांत संख्या विभाजन