Balanced number partitioning
संतुलित संख्या विभाजन बहु-मार्ग संख्या विभाजन का एक प्रकार है जिसमें प्रत्येक समूह को आवंटित वस्तुओं की संख्या पर प्रतिबंध होते हैं। समस्या के लिए इनपुट विभिन्न आकारों के n वस्तुओं का एक समूह है, और दो पूर्णांक m, k. आउटपुट वस्तुओं का m उपसमुच्चय में विभाजन है, जैसे कि प्रत्येक उपसमुच्चय में वस्तुओं की संख्या अधिकतम k है। इसके अधीन, यह आवश्यक है कि m उपसमुच्चय में आकारों का योग यथासंभव समान हो। एक उदाहरण अनुप्रयोग समान-मशीन अनुसूचना है जहाँ प्रत्येक मशीन में एक नौकरी-क्यू होता है जो अधिकतम के नौकरियों को धारण कर सकता है। वी. एल. एस. आई. चिपों के निर्माण और लचीली विनिर्माण प्रणालियों में मशीनों को उपकरण सौंपने में भी इस समस्या के अनुप्रयोग हैं। इष्टतम कार्य समय निर्धारण समस्याओं के लिए मानक तीन-क्षेत्र संकेतन में, सबसे बड़ी राशि को कम करने की समस्या को कभी-कभी "पी। #≤ के। सीमैक्स" द्वारा दर्शाया जाता है। मध्य क्षेत्र "#≤ k" इंगित करता है कि प्रत्येक मशीन में नौकरियों की संख्या अधिकतम k होनी चाहिए। यह अनियंत्रित संस्करण के विपरीत है, जिसे "" द्वारा दर्शाया जाता है। दो-तरफा संतुलित विभाजन एक सामान्य विशेष मामला जिसे दो-तरफा संतुलित विभाजन कहा जाता है, वह है जब दो उपसमुच्चय (m = 2) होने चाहिए। दोनों उपसमुच्चय में फर्श (एन/2) और छत (एन/2) आइटम होने चाहिए। यह विभाजन समस्या का एक प्रकार है। यह तय करना एन. पी.-कठिन है कि क्या कोई विभाजन मौजूद है जिसमें दो उपसमुच्चय में योग बराबर हैं; समस्या [एस. पी. 12] देखें। ऐसे कई एल्गोरिदम हैं जिनका उद्देश्य एक संतुलित विभाजन खोजना है जिसमें योग यथासंभव लगभग समान हो। कॉफ़मैन, फ्रेडरिकसन और ल्यूकर एल. पी. टी. एल्गोरिदम (जिसे आर. एल. पी. टी. कहा जाता है) का एक प्रतिबंधित संस्करण प्रस्तुत करते हैं, जिसमें इनपुट को जोड़े में सौंपा जाता है। जब निवेश समान रूप से वितरित यादृच्छिक चर होते हैं, तो आरएलपीटी का अपेक्षित सबसे बड़ा योग ठीक होता है। अपेक्षित कार्य-अंतर (सबसे बड़ी और सबसे छोटी राशि के बीच का अंतर) है। ल्यूकर एल. डी. एम. एल्गोरिदम का एक प्रकार प्रस्तुत करता है (जिसे जोड़ीदार विभेदक विधि (पी. डी. एम.) कहा जाता है)। इसका अपेक्षित कार्य-अंतर है। त्साई एक एल्गोरिथ्म प्रस्तुत करती है जिसे प्रतिबंधित सबसे बड़ा अंतर (आरएलडी) कहा जाता है। इसका कार्य-अंतर लगभग निश्चित है। याकिर एम = 2 के लिए एल. डी. एम. एल्गोरिथम का एक संतुलित संस्करण प्रस्तुत करता है, जिसे बी. एल. डी. एम. कहा जाता है। इसका अपेक्षित कार्य-अंतर है। मर्टेंस संतुलित दो-तरफा विभाजन के लिए किसी भी समय एक पूर्ण एल्गोरिथ्म प्रस्तुत करता है। यह बी. एल. डी. एम. एल्गोरिदम को पूर्ण-कर्मकार-कार्प एल्गोरिदम के साथ जोड़ता है। एक अन्य विशेष मामला जिसे 3-विभाजन कहा जाता है, वह है जब प्रत्येक उपसमुच्चय में वस्तुओं की संख्या अधिकतम 3 (के = 3) होनी चाहिए। यह तय करना कि क्या समान राशियों के साथ ऐसा विभाजन मौजूद है, बिल्कुल 3-विभाजन समस्या है, जिसे दृढ़ता से एन. पी.-हार्ड के रूप में जाना जाता है। ऐसे सन्निकटन एल्गोरिदम हैं जिनका उद्देश्य एक विभाजन खोजना है जिसमें योग यथासंभव लगभग समान हो। केलर और वोजिंगर एल. पी. टी. एल्गोरिदम को तीन गुना विभाजन के लिए अनुकूलित करते हैं (जहां अधिक से अधिक 3 * मीटर आइटम होते हैं, और प्रत्येक सबसेट में अधिक से अधिक 3 आइटम होने चाहिए)। उनके एल्गोरिदम को संशोधित-एल. पी. टी. या एम. एल. पी. टी. कहा जाता है। यह वस्तुओं को बड़े से लेकर छोटे तक का ऑर्डर देता है, और प्रत्येक वस्तु को उन डिब्बों में सबसे छोटी राशि के साथ बिन में डालता है जिनमें 3 से कम वस्तुएं होती हैं। वे दिखाते हैं कि एम. एल. पी. टी. एल्गोरिदम अधिकांश न्यूनतम सबसे बड़ी राशि प्राप्त करता है, जो कि वही सन्निकटन अनुपात है जो एल. पी. टी. अनियंत्रित समस्या के लिए प्राप्त करता है। एम. एल. पी. टी. के लिए सीमा कड़ी है। चेन, हे और लिन दिखाते हैं कि, एक ही समस्या के लिए, एम. एल. पी. टी. कम से कम अधिकतम सबसे छोटी राशि प्राप्त करता है, जो फिर से वही अनुपात है जो एल. पी. टी. अनियंत्रित समस्या के लिए प्राप्त करता है। केलर और कोटोव एक अलग एल्गोरिथ्म प्रस्तुत करते हैं (ठीक 3 * मीटर वस्तुओं के मामले के लिए), जो न्यूनतम सबसे बड़ी राशि को प्राप्त करता है। एक अधिक सामान्य मामला, जिसे के-विभाजन कहा जाता है, वह है जब प्रत्येक उपसमुच्चय में वस्तुओं की संख्या अधिकतम के होनी चाहिए, जहां के कोई भी सकारात्मक पूर्णांक हो सकता है। बेबल, केलर और कोटोव एक प्रकार का अध्ययन करते हैं जिसमें के × एम आइटम होते हैं (कुछ पूर्णांक के लिए), और प्रत्येक एम सेट में बिल्कुल के आइटम होने चाहिए। वे न्यूनतम सबसे बड़े योग को अनुमानित करने के लिए कई ह्यूरिस्टिक एल्गोरिदम प्रस्तुत करते हैंः फोल्डिंग एल्गोरिदमः एम = 2 के लिए इष्टतम, और सामान्य रूप से तंग सन्निकटन अनुपात होता है। विनिमय एल्गोरिथः तंग सन्निकटन अनुपात। यह ज्ञात नहीं है कि यह बहुपद समय में चलता है या नहीं। प्राइमल-डुअल एल्गोरिथ्म (एल. पी. टी. और मल्टीफिट का एक संयोजन): अधिकतम अनुमानित अनुपात। यह k = 4 के लिए तंग होता है जब m पर्याप्त रूप से बड़ा होता है; सटीक निचली सीमा है)। यह भी अनुमान है कि संशोधित-एल. पी. टी. का एक अनुमानित अनुपात है। वर्तमान में, यह अनुमान केवल k = 3 के लिए ही सही माना जाता है। के> 3 के लिए, यह ज्ञात है कि इसका सन्निकटन अनुपात अधिकतम 2 है। मिशेल, कोर्स्ट, आर्ट्स, वैन लीउवेन और स्पिक्समा एक प्रकार का अध्ययन करते हैं जिसमें प्रत्येक एम सेट में या तो छत (एन/एम) या फर्श (एन/एम) आइटम होने चाहिए (इसलिए के = छत (एन/एम))। वे संतुलित-एल. डी. एम. (बी. एल. डी. एम.) को एम = 2 से सामान्य एम तक विस्तारित करते हैं। सामान्यीकृत एल्गोरिथ्म समय पर चलता है। वे साबित करते हैं कि न्यूनतम सबसे बड़ी राशि के लिए इसका सन्निकटन अनुपात k = 3 के लिए 4/3, k = 4 के लिए 19/12, k = 5 के लिए 103/60, k = 6 के लिए 643/360 और k = 7 के लिए 4603/2520 है। एक मिश्रित पूर्णांक रैखिक कार्यक्रम को हल करके अनुपात पाए गए। सामान्य तौर पर (किसी भी के के लिए), सन्निकटन अनुपात कम से कम और अधिक से अधिक होता है। 3,4,5,6,7 के लिए सटीक एम. आई. एल. पी. परिणाम निचली सीमा के अनुरूप हैं। के> 7 के लिए, कोई सटीक परिणाम ज्ञात नहीं हैं, लेकिन निचले और ऊपरी सीमा के बीच का अंतर 0.3% से कम है। जब पैरामीटर सबसेट (एम) की संख्या है, तो सन्निकटन अनुपात बिल्कुल है। झांग, मौरातिडिस और पांग बताते हैं कि बी. एल. डी. एम. उच्च कार्य-अंतर (उच्चतम और न्यूनतम राशि के बीच अंतर) के साथ विभाजन प्राप्त कर सकता है, दोनों जब निवेश समान रूप से वितरित किए जाते हैं, और जब उनका वितरण तिरछा होता है। वे दो वैकल्पिक शोध का प्रस्ताव करते हैंः एल. आर. एम. कार्य-अंतर को बी. एल. डी. एम. के कार्य-अंतर के 1/3 तक कम कर देता है जब वितरण समान होता है; जब वितरण तिरछा होता है तो मेल्ड कार्य-अंतर को कम कर देता है। एक संकर एल्गोरिथ्म बी. एल. डी. एम., एल. आर. एम. और मेल्ड को जोड़ता है और विभिन्न डेटा वितरणों के लिए गतिशील रूप से अनुकूलित करता है। जब के स्थिर होता है, तो संतुलित विभाजन के लिए होचबाम और स्मॉय के पी. टी. ए. एस. का उपयोग किया जा सकता है। जब k इनपुट का हिस्सा होता है, तो वर्तमान में कोई पी. टी. ए. एस. ज्ञात नहीं है। डेल 'एमिको और मार्टेलो सबसे बड़ी राशि को कम करने की समस्या का अध्ययन करते हैं जब सभी सेटों में वस्तुओं की संख्या अधिकतम k होती है। वे बताते हैं कि इस संस्करण के रैखिक-कार्यक्रम छूट का समान इष्टतम मूल्य है जो अनियंत्रित संस्करण के एल. पी. छूट का है। अभिव्यक्ति, जहाँ xi बड़े से छोटे तक के आदेशित निवेश हैं, इष्टतम सबसे बड़ी राशि के लिए एक निचली सीमा है, और इसका सबसे खराब स्थिति अनुपात दोनों रूपों में 1/2 है। उन्नत अभिव्यक्ति का सबसे खराब स्थिति अनुपात अनियंत्रित संस्करण में 2/3 और बाधित संस्करण में 1/2 है। अनियंत्रित संस्करण के लिए संशोधित सूची शेड्यूलिंग का अनुमानित अनुपात 1/2 है, लेकिन यह सीमित संस्करण के लिए 0 है (यह मनमाने ढंग से खराब हो सकता है)। संशोधित एल. पी. टी. एल्गोरिदम का सन्निकटन अनुपात अधिकतम 2 है। वे यह भी दर्शाते हैं कि की निचली सीमा में 3/4 का एक तंग सबसे खराब स्थिति प्रदर्शन अनुपात है, और उनके पीडी एल्गोरिथ्म में 4/3 का एक तंग प्रदर्शन अनुपात है (जब एम पर्याप्त रूप से बड़ा है)। वह, तान, झू और याओ सबसे छोटी राशि को अधिकतम करने की समस्या पर विचार करते हैं। वे दिखाते हैं कि फ़ोल्डिंग एल्गोरिथ्म में तंग सन्निकटन अनुपात है। वे कम से कम सबसे खराब स्थिति अनुपात के साथ एक नया एल्गोरिथ्म, हार्मोनिक 1 प्रस्तुत करते हैं। ये दोनों एल्गोरिदम क्रमिक हैं-वे वस्तुओं को उनके सटीक मूल्यों के बजाय केवल उनके बीच के क्रम के आधार पर विभाजित करते हैं। वे साबित करते हैं कि किसी भी क्रमिक एल्गोरिथ्म में सबसे छोटे योग को अधिकतम करने के लिए अनुपात होता है। यह इंगित करता है कि हार्मोनिक1 असिम्प्टोटिक रूप से इष्टतम है। किसी भी निश्चित k के लिए, किसी भी क्रमिक एल्गोरिथ्म का अनुपात समीकरण का सबसे छोटा मूल होता है। जब k अनंत की ओर जाता है, तो यह ऊपरी सीमा 0 तक पहुंच जाती है। संतुलित और अनियंत्रित समस्याओं के बीच संबंध संतुलित विभाजन समस्या और मानक (अनियंत्रित) विभाजन समस्या के सन्निकटन के बीच कुछ सामान्य संबंध हैं। बेबल, केलर और कोटोव साबित करते हैं कि अनियंत्रित इष्टतम और सीमित इष्टतम के बीच का अनुपात अधिक से अधिक है, और यह तंग है। केलर और कोटोव यह साबित करते हैं कि क्षमता k और सन्निकटन-अनुपात r (न्यूनतम सबसे बड़ी राशि के लिए) के साथ संतुलित विभाजन के लिए प्रत्येक शोध का उपयोग सन्निकटन-अनुपात के साथ अनियंत्रित विभाजन के लिए एक शोध प्राप्त करने के लिए किया जा सकता है। विशेष रूप से, ट्रिपल विभाजन (के = 3) के लिए उनके-सन्निकटन एल्गोरिदम का उपयोग सन्निकटन-अनुपात के साथ अनियंत्रित विभाजन के लिए एक शोध प्राप्त करने के लिए किया जा सकता है। विभिन्न कार्डिनलिटी बाधाएं कार्डिनलिटी बाधाओं को प्रत्येक सबसेट पर एक अलग बाधा की अनुमति देकर सामान्यीकृत किया जा सकता है। इस संस्करण को "खुली समस्याओं" के खंड में पेश किया गया है, जो की-विभाजन समस्या को कहते हैं। वह, टैन, झू और याओ विभिन्न कार्डिनलिटी बाधाओं के साथ सबसे छोटे योग को अधिकतम करने के लिए हार्मोनिक 2 नामक एक एल्गोरिथ्म प्रस्तुत करते हैं। वे साबित करते हैं कि इसका सबसे खराब स्थिति अनुपात कम से कम है। कार्डिनलिटी बाधाओं को वर्गीकृत करना कार्डिनलिटी बाधाओं का एक और सामान्यीकरण इस प्रकार है। इनपुट वस्तुओं को के श्रेणियों में विभाजित किया गया है। प्रत्येक श्रेणी एच के लिए, एक क्षमता बाधा केएच है। प्रत्येक एम सबसेट में श्रेणी एच से अधिकतम केएच आइटम हो सकते हैं। दूसरे शब्दों मेंः सभी एम सबसेट एक विशेष विभाजन मैट्रायड का स्वतंत्र सेट होना चाहिए। इस समस्या के दो विशेष मामलों का अध्ययन किया गया है। कर्नेल विभाजन कर्नेल संतुलित-विभाजन समस्या में, कुछ m पूर्व-निर्दिष्ट आइटम कर्नेल होते हैं, और प्रत्येक m उपसमुच्चय में एक एकल कर्नेल (और असीमित संख्या में गैर-कर्नेल) होना चाहिए। यहाँ, दो श्रेणियाँ हैंः क्षमता 1 के साथ कर्नेल श्रेणी, और असीमित क्षमता के साथ गैर-कर्नेल श्रेणी। चेन, हे और याओ साबित करते हैं कि k = 3 के लिए भी समस्या NP-कठिन है (k = 2 के लिए इसे अधिकतम वजन मिलान ढूंढकर कुशलता से हल किया जा सकता है)। इसके बाद वे कर्नेल-एल. पी. टी. (के. एल. पी. टी.) नामक एक एल्गोरिथ्म प्रस्तुत करते हैंः यह प्रत्येक सबसेट को एक कर्नेल प्रदान करता है, और फिर संशोधित एल. पी. टी. एल्गोरिथ्म चलाता है (प्रत्येक वस्तु को सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ सबसे छोटे योग के साथ वे साबित करते हैं कि, के = 3 के साथ, के. एल. पी. टी. का न्यूनतम सबसे बड़ी राशि के लिए एक अनुमानित अनुपात है। हालांकि, चेन, हे और लिन का दावा है कि इसका तंग सन्निकटन अनुपात न्यूनतम सबसे बड़ी राशि और अधिकतम सबसे छोटी राशि के लिए है। एक-प्रति-श्रेणी विभाजन इस समस्या के एक अन्य संस्करण में, आकार m की कुछ k श्रेणियां हैं, और प्रत्येक उपसमुच्चय में प्रत्येक श्रेणी से बिल्कुल एक वस्तु होनी चाहिए। अर्थात्, प्रत्येक श्रेणी एच के लिए केएच = 1। वू और याओ ने स्तरित एलपीटी एल्गोरिथ्म प्रस्तुत किया-एलपीटी एल्गोरिथ्म का एक प्रकार। वे साबित करते हैं कि इसका सन्निकटन अनुपात सबसे बड़ी राशि को कम करने के लिए है; सामान्य मामले में सबसे छोटी राशि को अधिकतम करने के लिए; और कुछ विशेष मामलों में, सामान्य k के लिए और k = 3 के लिए सुधार किया जा सकता है। ली और ली ने एक ही समस्या के लिए अलग-अलग एल्गोरिदम प्रस्तुत किए। सबसे बड़े योग को न्यूनतम करने के लिए, वे स्थिरांक k के लिए एक EPTAS और स्थिरांक m के लिए एक FPTAS प्रस्तुत करते हैं। सबसे छोटे योग को अधिकतम करने के लिए, वे सामान्य मामले के लिए एक 1/(k−1) सन्निकटन एल्गोरिथ्म और स्थिरांक k के लिए एक EPTAS प्रस्तुत करते हैं। वे एक अधिक सामान्य उद्देश्य का भी अध्ययन करते हैंः योग के सदिश के lp-मानक को न्यूनतम करना। वे साबित करते हैं कि स्तरित-एल. पी. टी. एल्गोरिदम सभी मानदंडों के लिए एक 2-सन्निकटन एल्गोरिदम है। डेल 'ओल्मो, हैनसेन, पैलोटिनो और स्टोर्ची इस समस्या के लिए 32 अलग-अलग उद्देश्यों का अध्ययन करते हैं। चार प्रचालकों में से प्रत्येक के लिए अधिकतम, न्यूनतम, योग, अंतर, प्रत्येक उपसमुच्चय के अंदर के वस्तुओं पर एक प्रचालक लागू किया जा सकता है, और फिर विभिन्न उपसमुच्चय के लिए एम परिणामों पर एक प्रचालक लागू किया जा सकता है। इन 16 उद्देश्यों में से प्रत्येक को कुल 32 के लिए अधिकतम या न्यूनतम किया जा सकता है। वे बताते हैं कि इनमें से 21 समस्याओं को रैखिक समय में हल किया जा सकता है; 7 के लिए अधिक जटिल, लेकिन फिर भी बहुपद-समय, एल्गोरिदम की आवश्यकता होती है; 3 एन. पी.-हार्ड हैंः अधिकतम (न्यूनतम, योग), न्यूनतम (अधिकतम, योग) और न्यूनतम (अंतर, योग)। उन्होंने न्यूनतम करने की स्थिति (अंतर, अंतर) को खुला छोड़ दिया। यह भी देखें कि मेट्रॉइड-सीमित संख्या विभाजन एक सामान्यीकरण है जिसमें एक निश्चित मेट्रॉइड को एक पैरामीटर के रूप में दिया जाता है, और प्रत्येक एम सबसेट इस मेट्रॉइड का एक स्वतंत्र सेट या आधार होना चाहिए। कार्डिनलिटी बाधाएं मैट्रायड बाधाओं के विशेष मामले हैं जिनमें मैट्रायड एक समान मैट्रायड है। वर्गीकृत कार्डिनलिटी बाधाएं एक विशेष मामला है जिसमें मैट्रायड एक विभाजन मैट्रायड है। संदर्भ संख्या विभाजन