Karmarkar–Karp bin packing algorithms
करमरकर-कार्प (केके) बिन पैकिंग एल्गोरिदम बिन पैकिंग समस्या के लिए कई संबंधित सन्निकटन एल्गोरिदम हैं। बिन पैकिंग की समस्या विभिन्न आकारों की वस्तुओं को समान क्षमता के डिब्बे में पैक करने की समस्या है, जैसे कि डिब्बे की कुल संख्या यथासंभव कम हो। इष्टतम समाधान खोजना कम्प्यूटेशनल रूप से कठिन है। करमरकर और कार्प ने एक एल्गोरिथ्म तैयार किया जो बहुपद समय में चलता है और अधिकतम डिब्बे के साथ एक समाधान ढूंढता है, जहां ऑप्ट इष्टतम समाधान में डिब्बे की संख्या है। उन्होंने कुछ अलग सन्निकटन गारंटी और रन-टाइम सीमा के साथ कई अन्य एल्गोरिदम भी तैयार किए। के. के. एल्गोरिदम को बिन पैकिंग के अध्ययन में एक सफलता माना गया थाः पहले से ज्ञात एल्गोरिदम ने गुणक सन्निकटन पाया, जहां कुछ स्थिरांकों के लिए डिब्बे की संख्या अधिक से अधिक या अधिक से अधिक थी। के. के. एल्गोरिदम सबसे पहले एक योगात्मक सन्निकटन प्राप्त करने वाले थे। बिन-पैकिंग समस्या के लिए इनपुट विभिन्न आकारों की वस्तुओं का एक समूह है, a1,. an। निम्नलिखित संकेतन का उपयोग किया जाता हैः एन-वस्तुओं की संख्या। एम-विभिन्न वस्तु आकारों की संख्या। 1 में प्रत्येक i के लिए, m: si i-th आकार है; ni आकार की वस्तुओं की संख्या है। बी-बिन का आकार। एक उदाहरण I को देखते हुए, हम दर्शाते हैंः ओ. पी. टी. (I) = उदाहरण I का इष्टतम समाधान. एफ. ओ. पी. टी. (I) = (ए1 +. + ए)/बी = सैद्धांतिक रूप से डिब्बों की इष्टतम संख्या, जब सभी डिब्बे पूरी तरह से वस्तुओं या वस्तु अंशों से भरे होते हैं। जाहिर है, एफ. ओ. पी. टी. (I) ≤ ओ. पी. टी. (I)। उच्च-स्तरीय योजना केके एल्गोरिदम अनिवार्य रूप से विन्यास रैखिक कार्यक्रम को हल करते हैंः यहाँ, ए एम पंक्तियों के साथ एक मैट्रिक्स है। ए का प्रत्येक स्तंभ एक व्यवहार्य विन्यास का प्रतिनिधित्व करता है-वस्तु-आकारों का एक बहु-समूह, जैसे कि इन सभी आकारों का योग अधिकतम बी है। विन्यासों का समुच्चय सी है. एक्स आकार सी का एक सदिश है। एक्स का प्रत्येक तत्व xc विन्यास सी का उपयोग किए जाने की संख्या को दर्शाता है। उदाहरण के लिएः मान लीजिए कि वस्तु का आकार 3,3,3,3,3,4,4,4,4,4, और B = 12 है। फिर सी = 10 संभावित विन्यास हैंः 3333; 333; 33,334,344; 4,44,444। मैट्रिक्स ए में दो पंक्तियाँ हैंः [4,3,2,2,1,1,1,0,0,0] s = 3 के लिए और [0,0,0,1,0,1,2,1,2,3] s = 4 के लिए। वेक्टर एन [5,5] है क्योंकि प्रत्येक आकार के 5 आइटम हैं। एक संभावित इष्टतम समाधान x = [1,0,0,0,0,0,1,0,0,1] है, जो विन्यास 3333,344,444 के साथ तीन डिब्बे का उपयोग करने के अनुरूप है। इस समस्या को हल करने में दो मुख्य कठिनाइयाँ हैं। सबसे पहले, यह एक पूर्णांक रैखिक कार्यक्रम है, जिसे हल करना कम्प्यूटेशनल रूप से कठिन है। दूसरा, चरों की संख्या सी है-विन्यासों की संख्या, जो बहुत अधिक हो सकती है। केके एल्गोरिदम कई तकनीकों का उपयोग करके इन कठिनाइयों का सामना करते हैं, जिनमें से कुछ पहले से ही डी-ला-वेगा और ल्यूकर द्वारा पेश की गई थीं। यहाँ एल्गोरिथ्म का एक उच्च-स्तरीय विवरण दिया गया है (जहाँ मूल उदाहरण है): 1-ए। मान लीजिए कि इसे छोटी वस्तुओं को हटाकर बनाया गया है। 2-ए। मान लीजिए कि वस्तुओं को समूहबद्ध करके और प्रत्येक समूह में वस्तुओं के आकार को समूह में उच्चतम वस्तु के साथ गोल करके एक उदाहरण बनाया गया है। 3-ए। समाकलन बाधाओं के बिना, विन्यास रैखिक कार्यक्रम का निर्माण करें। 4. रिलैक्सड लीनियर प्रोग्राम के लिए a (फ्रैक्शनल) समाधान x की गणना करें। 3-बी। के लिए एक अभिन्न समाधान के लिए x को गोल करें। 2-बी। समाधान प्राप्त करने के लिए वस्तुओं को "अन-ग्रुप" करें। 1-बी। समाधान प्राप्त करने के लिए छोटी वस्तुओं को जोड़ें। नीचे, हम इनमें से प्रत्येक चरण का बारी-बारी से वर्णन करते हैं। चरण 1. छोटी वस्तुओं को हटाना और जोड़ना छोटी वस्तुओं को हटाने की प्रेरणा यह है कि जब सभी वस्तुएं बड़ी होती हैं, तो प्रत्येक बिन में वस्तुओं की संख्या कम होनी चाहिए, इसलिए संभावित विन्यास की संख्या (अपेक्षाकृत) कम होती है। हम कुछ स्थिरांक चुनते हैं, और मूल उदाहरण से उससे छोटी सभी वस्तुओं को हटा देते हैं। मान लीजिए कि यह परिणामी उदाहरण है। ध्यान दें कि प्रत्येक बिन में अधिकांश वस्तुएँ हो सकती हैं। हम पैक करते हैं और कुछ डिब्बों के साथ एक पैकिंग प्राप्त करते हैं। अब, हम छोटी वस्तुओं को मौजूदा डिब्बे में मनमाने क्रम में जोड़ते हैं, जब तक कि जगह हो। जब मौजूदा डिब्बे में और जगह नहीं होती है, तो हम एक नया बिन खोलते हैं (जैसा कि अगले-फिट बिन पैकिंग में होता है)। अंतिम पैकिंग में डिब्बों की संख्या मान लीजिए। फिरः सबूत। यदि कोई नया डिब्बे नहीं खोला जाता है, तो डिब्बों की संख्या बनी रहती है। यदि एक नया बिन खोला जाता है, तो शायद अंतिम को छोड़कर सभी डिब्बों में कम से कम कुल आकार होता है, इसलिए कुल उदाहरण आकार कम से कम होता है। इसलिए, इष्टतम समाधान के लिए कम से कम डिब्बे की आवश्यकता होती है। तो। विशेष रूप से, g = 1/n लेने से, हम प्राप्त करते हैंः, क्योंकि। इसलिए, यह मान लेना आम बात है कि सभी वस्तुएँ 1/n से बड़ी हैं। चरण 2. वस्तुओं को समूहीकृत और गैर-समूहीकृत करना वस्तुओं को समूहीकृत करने की प्रेरणा विभिन्न वस्तुओं के आकारों की संख्या को कम करना है, ताकि विन्यास एल. पी. में बाधाओं की संख्या को कम किया जा सके। समूहीकरण की सामान्य प्रक्रिया हैः घटते आकार के आधार पर वस्तुओं का आदेश दें। वस्तुओं को समूहों में विभाजित करें। प्रत्येक समूह के लिए, समूह में सभी वस्तुओं के आकार को समूह में सबसे बड़े आकार में संशोधित करें। समूहीकरण की कई अलग-अलग विधियाँ हैं। रैखिक समूहीकरण एक पूर्णांक पैरामीटर होने दें। सबसे बड़ी वस्तुओं को समूह 1 में रखें; समूह 2 में अगली सबसे बड़ी वस्तुएँ; और इसी तरह (अंतिम समूह में वस्तुओं से कम हो सकती हैं)। मूल उदाहरण लीजिए। मान लीजिए कि पहला समूह (सबसे बड़ी वस्तुओं का समूह), और पहले समूह के बिना समूहबद्ध उदाहरण। फिरः सभी वस्तुओं का आकार समान होता है। विभिन्न आकारों की संख्या में है। - चूंकि समूह 1 में समूह 2 का प्रभुत्व है (समूह 1 में सभी के आइटम समूह 2 में के आइटम से बड़े हैं); इसी तरह, समूह 2 में समूह 3 में आदि का प्रभुत्व है। - क्योंकि प्रत्येक वस्तु को एक ही डिब्बे में पैक करना संभव है। इसलिए,। वास्तव में, डिब्बे के साथ समाधान दिए जाने पर, हम अधिक से अधिक डिब्बे के साथ समाधान प्राप्त कर सकते हैं। ज्यामितीय समूहीकरण एक पूर्णांक पैरामीटर होने दें। ज्यामितीय समूहीकरण दो चरणों में आगे बढ़ता हैः उदाहरण को कई उदाहरणों में इस तरह विभाजित करें कि, प्रत्येक उदाहरण में, सभी आकार अंतराल में हों। ध्यान दें कि, यदि सभी वस्तुओं का आकार कम से कम है, तो उदाहरणों की संख्या अधिक से अधिक है। प्रत्येक उदाहरण पर, पैरामीटर के साथ रैखिक राउंडिंग करें। मान लीजिए कि परिणामी उदाहरण हैं। चलो और। फिर, विभिन्न आकारों की संख्या निम्नानुसार सीमित हैः सभी आर के लिए, और। चूँकि सभी वस्तुएँ उससे बड़ी हैं, इसलिए हमारे पास हैं। सभी आर का सारांश देता है। डिब्बों की संख्या निम्नानुसार सीमित हैः सभी आर के लिए,-क्योंकि इसमें आइटम हैं, और वे सभी उससे छोटे हैं, इसलिए उन्हें अधिकांश डिब्बों में पैक किया जा सकता है। इसलिए,। इसलिए,। वैकल्पिक ज्यामितीय समूह एक पूर्णांक पैरामीटर होने दें। वस्तुओं को अवरोही आकार से ऑर्डर करें। उन्हें समूहों में इस तरह विभाजित करें कि प्रत्येक समूह में कुल आकार कम से कम हो। चूँकि प्रत्येक वस्तु का आकार बी से कम है, इसलिए प्रत्येक समूह में वस्तुओं की संख्या कम से कम है। प्रत्येक समूह में वस्तुओं की संख्या कमजोर रूप से बढ़ रही है। यदि सभी वस्तुएँ उससे बड़ी हैं, तो प्रत्येक समूह में वस्तुओं की संख्या अधिक से अधिक है। प्रत्येक समूह में, केवल बड़ी वस्तुओं को गोल किया जाता है। यह इस तरह से किया जा सकता है किः .. चरण 3. एल. पी. का निर्माण और समाधान को गोल करना हम समाकलन बाधाओं के बिना विन्यास रैखिक कार्यक्रम पर विचार करते हैंः यहाँ, हमें प्रत्येक विन्यास की एक आंशिक संख्या का उपयोग करने की अनुमति है। उदाहरण के लिएः मान लीजिए कि आकार 3 की 31 वस्तुएँ और आकार 4 की 7 वस्तुएँ हैं, और बिन-आकार 10 है। विन्यास इस प्रकार हैंः 4,44,34,334,33,333। बाधाएँ हैं [0,0,1,2,1,2,3] * x = 31 और [1,2,1,1,0,0,0] * x = 7। भिन्नात्मक एल. पी. का एक इष्टतम समाधान है [0,0,0,7,0,0,17/3] अर्थात्ः विन्यास 334 के 7 डिब्बे और विन्यास 333 के 17/3 डिब्बे हैं। ध्यान दें कि केवल दो अलग-अलग विन्यासों की आवश्यकता है। एल. ओ. पी. टी. द्वारा रैखिक कार्यक्रम के इष्टतम समाधान को निरूपित करें। निम्नलिखित संबंध स्पष्ट हैंः एफओपीटी (आई) ≤ एलओपीटी (आई), क्योंकि एफओपीटी (आई) डिब्बों की (संभवतः आंशिक) संख्या है जब सभी डिब्बे पूरी तरह से वस्तुओं या वस्तुओं के अंशों से भरे होते हैं। स्पष्ट रूप से, कोई भी समाधान अधिक प्रभावी नहीं हो सकता है। एल. ओ. पी. टी. (I) ≤ ओ. पी. टी. (I), क्योंकि एल. ओ. पी. टी. (I) कम बाधाओं के साथ एक न्यूनतम समस्या का समाधान है। ओ. पी. टी. (I) <2 * एफ. ओ. पी. टी. (I), क्योंकि कम से कम 2 * एफ. ओ. पी. टी. (I) डिब्बों वाले किसी भी पैकिंग में, दो कम से कम भरे हुए डिब्बों का योग अधिकतम बी होता है, इसलिए उन्हें एक ही बिन में जोड़ा जा सकता है। भिन्नात्मक एल. पी. के समाधान को निम्नानुसार एक अभिन्न समाधान के लिए गोल किया जा सकता है। मान लीजिए कि हमारे पास भिन्न एल. पी. का समाधान x है। हम इंटीग्रल आई. एल. पी. के लिए एक समाधान में x को निम्नानुसार राउंड करते हैं। मान लीजिए कि x भिन्नात्मक LP का एक इष्टतम बुनियादी व्यवहार्य समाधान है। मान लीजिए कि यह डिब्बे के रूप में है (ध्यान दें कि यह एक आंशिक संख्या हो सकती है)। चूँकि भिन्नात्मक एल. पी. में एम बाधाएँ होती हैं (प्रत्येक विशिष्ट आकार के लिए एक), एक्स में अधिकतम एम गैर-शून्य चर होते हैं, अर्थात, अधिकतम एम अलग-अलग विन्यासों का उपयोग किया जाता है। हम x से एक अभिन्न पैकिंग का निर्माण करते हैं जिसमें एक प्रमुख भाग और एक अवशिष्ट भाग होता है। मुख्य भाग में प्रत्येक विन्यास सी के फर्श (एक्ससी) डिब्बे होते हैं जिनके लिए एक्ससी> 0 होता है। अवशिष्ट भाग (आर द्वारा निरूपित) के लिए, हम दो उम्मीदवार पैकेजिंग का निर्माण करते हैंः प्रत्येक विन्यास सी का एक एकल बिन जिसके लिए xc> 0; सभी एम डिब्बे की आवश्यकता होती है। 2 * एफ. ओ. पी. टी. (आर) डिब्बे से कम के साथ एक लालची पैकिंग (क्योंकि यदि कम से कम 2 * एफ. ओ. पी. टी. (आर) डिब्बे हैं, तो दो सबसे छोटे डिब्बों को जोड़ा जा सकता है)। इनमें से सबसे छोटे पैकेजिंग के लिए न्यूनतम (एम, 2 * एफओपीटी (आर)) ≤ औसत (एम, 2 * एफओपीटी (आर)) = एफओपीटी (आर) + एम/2 की आवश्यकता होती है। इसे जोड़ते हुए मुख्य भाग के गोल-डाउन डिब्बे से अधिकांश डिब्बों में उपज मिलती है। इस रूपांतरण एल्गोरिथ्म का निष्पादन समय ओ (एन लॉग एन) है। इसका अर्थ यह भी है। चरण 4. भिन्नात्मक एल. पी. को हल करना भिन्नात्मक एल. पी. को हल करने में मुख्य चुनौती यह है कि इसमें बड़ी संख्या में चर हो सकते हैं-प्रत्येक संभावित विन्यास के लिए एक चर। दोहरे एल. पी. भिन्नात्मक एल. पी. का दोहरे रैखिक कार्यक्रम हैः इसमें एम चर हैं, और सी बाधाएं हैं-प्रत्येक विन्यास के लिए एक बाधा। इसकी निम्नलिखित आर्थिक व्याख्या है। प्रत्येक आकार एस के लिए, हमें एक गैर-नकारात्मक मूल्य निर्धारित करना चाहिए। हमारा लाभ सभी वस्तुओं की कुल कीमत है। हम इन बाधाओं के अधीन लाभ को अधिकतम करना चाहते हैं कि प्रत्येक विन्यास में वस्तुओं की कुल कीमत अधिकतम 1 हो। इस एल. पी. में अब केवल एम चर हैं, लेकिन बड़ी संख्या में बाधाएं हैं। यहां तक कि सभी बाधाओं को सूचीबद्ध करना भी असंभव है। सौभाग्य से, दीर्घवृत्त विधि के एक प्रकार का उपयोग करके, सभी बाधाओं को सूचीबद्ध किए बिना किसी भी सटीकता तक समस्या का समाधान करना संभव है। यह वैरिएंट इनपुट के रूप में मिलता है, एक पृथक्करण ऑरेकलः एक फ़ंक्शन जो, एक वेक्टर y ≤ 0 दिए जाने पर, निम्नलिखित दो विकल्पों में से एक को बताता हैः दावा करें कि y व्यवहार्य है, यानी, या-दावा करें कि y अव्यवहारिक है, और एक विशिष्ट बाधा को लौटाता है जिसका उल्लंघन किया जाता है, यानी, एक वेक्टर a ऐसा है। दीर्घवृत्त विधि एक बड़े दीर्घवृत्त से शुरू होती है, जिसमें संपूर्ण व्यवहार्य क्षेत्र शामिल होता है। प्रत्येक चरण टी पर, यह वर्तमान दीर्घवृत्त के केंद्र को लेता है, और इसे पृथक्करण दैवज्ञ को भेजता हैः यदि दैवज्ञ कहता है कि यह संभव है, तो हम एक "इष्टतमता कटौती" करते हैंः हम दीर्घवृत्त से सभी बिंदुओं को काटते हैं जिसके लिए y। ये बिंदु निश्चित रूप से इष्टतम नहीं हैं। यदि दैवज्ञ कहता है कि यह व्यवहार्य नहीं है और बाधा a का उल्लंघन करता है, तो हम एक "व्यवहार्यता कटौती" करते हैंः हम दीर्घवृत्त से सभी बिंदुओं y को काटते हैं जिसके लिए। ये बिंदु निश्चित रूप से संभव नहीं हैं। एक कट बनाने के बाद, हम एक नए, छोटे दीर्घवृत्त का निर्माण करते हैं। यह दिखाया जा सकता है कि यह प्रक्रिया आवश्यक सटीकता में समय बहुपद में एक अनुमानित समाधान में परिवर्तित हो जाती है। दोहरे एल. पी. के लिए एक पृथक्करण दैवज्ञ हमें कुछ एम गैर-नकारात्मक संख्याएँ दी गई हैं। हमें निम्नलिखित दो विकल्पों के बीच निर्णय लेना हैः प्रत्येक व्यवहार्य विन्यास के लिए, इस विन्यास के अनुरूप योग अधिक से अधिक 1 है; इसका मतलब है कि y व्यवहार्य है। एक व्यवहार्य विन्यास मौजूद है जिसके लिए योग 1 से बड़ा है; इसका मतलब है कि y अव्यवहारिक है। इस मामले में, हमें कॉन्फ़िगरेशन भी वापस करना होगा। इस समस्या को एक नापसैक समस्या को हल करके हल किया जा सकता है, जहां वस्तु के मूल्य हैं, वस्तु का वजन है, और वजन क्षमता बी (बिन का आकार) है। यदि इष्टतम नापसैक समाधान का कुल मूल्य अधिक से अधिक 1 है, तो हम कहते हैं कि y संभव है। यदि इष्टतम नापसैक समाधान का कुल मूल्य 1 से बड़ा है, तो हम कहते हैं कि y व्यवहार्य नहीं है, और इष्टतम नापसैक समाधान में आइटम एक विन्यास के अनुरूप हैं जो एक बाधा का उल्लंघन करता है (क्योंकि वेक्टर के लिए a जो इस विन्यास से मेल खाता है)। नैप्सैक समस्या को छद्म-बहुपद समय में गतिशील प्रोग्रामिंग द्वारा हल किया जा सकता हैः, जहाँ m निवेशों की संख्या है और V विभिन्न संभावित मूल्यों की संख्या है। एक बहुपद-समय एल्गोरिथ्म प्राप्त करने के लिए, हम इनपुट राउंडिंग का उपयोग करके लगभग नैप्सैक समस्या को हल कर सकते हैं। मान लीजिए कि हम सहिष्णुता के साथ समाधान चाहते हैं। हम प्रत्येक को/n के निकटतम गुणज तक गोल कर सकते हैं। फिर, 0 और 1 के बीच संभावित मानों की संख्या n/है, और रन-टाइम है। समाधान कम से कम इष्टतम समाधान माइनस/एन है। एक अनुमानित पृथक्करण दैवज्ञ के साथ दीर्घवृत्त विधि एक अनुमानित पृथक्करण दैवज्ञ का उपयोग करने के लिए दीर्घवृत्त विधि को अनुकूलित किया जाना चाहिए। वर्तमान दीर्घवृत्तीय केंद्र को देखते हुएः यदि अनुमानित दैवज्ञ 1 से बड़े मूल्य के साथ एक समाधान देता है, तो निश्चित रूप से व्यवहार्य नहीं है, और समाधान एक ऐसे विन्यास के अनुरूप है जो एक बाधा a का उल्लंघन करता है। हम एक "व्यवहार्यता कटौती" करते हैं, जिसके लिए सभी बिंदु y को काटते हैं। यदि अनुमानित दैवज्ञ अधिकतम 1 के मूल्य के साथ एक समाधान देता है, तो संभव हो सकता है या नहीं भी हो सकता है, लेकिन गोल करना (इसे दर्शाना) संभव है। राउंडिंग की परिभाषा के अनुसार, हम यह जानते हैं। हम अभी भी एक "इष्टतमता कटौती" करते हैंः हम दीर्घवृत्त से सभी बिंदुओं y को काटते हैं जिसके लिए। ध्यान दें कि यह व्यवहार्य नहीं हो सकता है, इसलिए इसका मूल्य ओ. पी. टी. से अधिक हो सकता है। इसलिए, हम कुछ बिंदुओं को हटा सकते हैं जिनका उद्देश्य इष्टतम है। हालाँकि, हटाए गए बिंदु संतुष्ट करते हैं; कोई भी बिंदु नहीं हटाया जाता है यदि इसका मूल्य मूल्य से अधिक हो जाता है। अनुमानित पृथक्करण दैवज्ञ का उपयोग करने से दोहरे एल. पी. के लिए एक व्यवहार्य समाधान y * मिलता है, जिसमें, अधिक से अधिक पुनरावृत्तियों के बाद, जहाँ। अनुमानित पृथक्करण दैवज्ञ के साथ दीर्घवृत्त विधि का कुल रन-टाइम है। बाधाओं को समाप्त करना दीर्घवृत्तीय विधि के दौरान, हम रूप की अधिकतम क्यू बाधाओं का उपयोग करते हैं। अन्य सभी बाधाओं को समाप्त किया जा सकता है, क्योंकि उनका दीर्घवृत्त विधि के परिणाम y * पर कोई प्रभाव नहीं पड़ता है। हम और भी अधिक बाधाओं को दूर कर सकते हैं। यह ज्ञात है कि, m चर वाले किसी भी LP में, m बाधाओं का एक समूह होता है जो इष्टतम समाधान निर्धारित करने के लिए पर्याप्त होता है (यानी, इष्टतम मूल्य समान होता है, भले ही केवल इन m बाधाओं का उपयोग किया जाए)। हम ऊपर के रूप में बार-बार दीर्घवृत्त विधि चला सकते हैं, हर बार बाधाओं के एक विशिष्ट समूह को दूर करने की कोशिश कर रहे हैं। यदि परिणामी त्रुटि अधिक से अधिक है, तो हम इन बाधाओं को स्थायी रूप से हटा देते हैं। यह दिखाया जा सकता है कि हमें अधिक से अधिक उन्मूलन की आवश्यकता है, इसलिए संचय त्रुटि अधिक से अधिक है। यदि हम निर्धारित रूप से बाधाओं के सेट का प्रयास करते हैं, तो सबसे खराब स्थिति में, एम परीक्षणों में से एक सफल होता है, इसलिए हमें अधिकांश समय पर दीर्घवृत्तीय विधि को चलाने की आवश्यकता होती है। यदि हम यादृच्छिक रूप से हटाने के लिए बाधाओं को चुनते हैं, तो पुनरावृत्तियों की अपेक्षित संख्या है। अंत में, हमारे पास एक कम दोहरी एल. पी. है, जिसमें केवल एम चर और एम बाधाएं हैं। कम एल. पी. का इष्टतम मूल्य कम से कम कहाँ है। प्राथमिक एल. पी. को हल करना एल. पी. द्वैतता प्रमेय द्वारा, प्राथमिक एल. पी. का न्यूनतम मान दोहरे एल. पी. के अधिकतम मूल्य के बराबर होता है, जिसे हम एल. ओ. पी. टी. द्वारा निरूपित करते हैं। एक बार जब हमारे पास एक कम दोहरी एल. पी. होती है, तो हम इसकी दोहरी लेते हैं, और एक कम प्राथमिक एल. पी. लेते हैं। इस एल. पी. में केवल एम चर हैं-सी विन्यासों में से केवल एम के अनुरूप। कम किए गए दोहरे एल. पी. का अधिकतम मूल्य कम से कम है। यह दिखाया जा सकता है कि कम प्राथमिक एल. पी. का इष्टतम समाधान अधिक से अधिक है। समाधान एक निकट-इष्टतम बिन पैकिंग देता है, जिसमें अधिकतम मीटर विन्यास का उपयोग किया जाता है। नियतात्मक एल्गोरिथम का कुल रन-टाइम, जब सभी आइटम उससे बड़े होते हैं, हैः यादृच्छिक एल्गोरिथम का अपेक्षित कुल रन-टाइम हैः एंड-टू-एंड एल्गोरिदम करमरकर और कार्प ने तीन एल्गोरिदम प्रस्तुत किए, जो विभिन्न मापदंडों के साथ उपरोक्त तकनीकों का उपयोग करते हैं। इन सभी एल्गोरिदम का रन-टाइम एक फ़ंक्शन पर निर्भर करता है, जो एक बहुपद फ़ंक्शन है जो सहिष्णुता h = 1 के साथ भिन्नात्मक LP को हल करने में लगने वाले समय का वर्णन करता है, जो कि निर्धारक संस्करण के लिए है। एल्गोरिदम 1 मान लीजिए कि वांछित सन्निकटन सटीकता का प्रतिनिधित्व करने वाला एक स्थिरांक हो। 1-ए। सेट करें। मान लीजिए कि ग्राम 2-ए से छोटी सभी वस्तुओं को हटाकर एक उदाहरण बनाया गया है। सेट करें। मान लीजिए कि k पैरामीटर के साथ रैखिक समूह द्वारा निर्मित एक उदाहरण है, और शेष उदाहरण (k सबसे बड़ी वस्तुओं का समूह) है। इस पर ध्यान दें। 3-ए। समाकलन बाधाओं के बिना, विन्यास रैखिक कार्यक्रम का निर्माण करें। 4. एक समाधान x की गणना करें, सहिष्णुता h = 1 के साथ। परिणाम डिब्बे के साथ एक आंशिक बिन पैकिंग है। रन-टाइम है। 3-बी। के लिए एक अभिन्न समाधान के लिए x को गोल करें। आंशिक भाग के लिए अधिकांश डिब्बे जोड़ें। डिब्बों की कुल संख्या है। 2-बी। अधिक से अधिक के डिब्बे में वस्तुओं को पैक करें; एक पैकिंग प्राप्त करें। डिब्बों की संख्या है। 1-बी। समाधान प्राप्त करने के लिए जी से छोटी वस्तुओं को जोड़ें। डिब्बों की संख्या हैः कुल मिलाकर, डिब्बे की संख्या अंदर है और रन-टाइम अंदर है। चुनने से हम प्राप्त करते हैं। एल्गोरिदम 2 आइए एक वास्तविक पैरामीटर और एक पूर्णांक पैरामीटर होने दें जिसे बाद में निर्धारित किया जाए। 1-ए। मान लीजिए कि जी. 2 से छोटी सभी वस्तुओं को हटाकर एक उदाहरण बनाया गया है। जबकि करते हैंः 2-ए। पैरामीटर k के साथ वैकल्पिक ज्यामितीय समूहीकरण करें। मान लीजिए कि यह परिणामी उदाहरण है, और शेष उदाहरण है। हमारे पास है। 3-ए। समाकलन बाधाओं के बिना, विन्यास रैखिक कार्यक्रम का निर्माण करें। 4. एक समाधान x की गणना करें, सहिष्णुता h = 1 के साथ। परिणाम डिब्बे के साथ एक आंशिक बिन पैकिंग है। रन-टाइम है। 3-बी। के लिए एक अभिन्न समाधान के लिए x को गोल करें। आंशिक भाग के लिए डिब्बे न जोड़ें। इसके बजाय, बस पैक की गई वस्तुओं को हटा दें। 2-बी। अधिकांश डिब्बों में वस्तुओं को पैक करें। 2. एक बार, शेष वस्तुओं को अधिकांश डिब्बों में लालच से पैक करें। चरण 2 में लूप के प्रत्येक पुनरावृत्ति पर, x के आंशिक भाग में अधिकतम m (K) पैटर्न होते हैं। एफ. ओ. पी. टी. प्रत्येक पुनरावृत्ति में के के कारक से गिरता है, इसलिए पुनरावृत्तियों की संख्या अधिक से अधिक है। इसलिए, उपयोग किए जाने वाले डिब्बों की कुल संख्या हैः 1-बी। समाधान प्राप्त करने के लिए जी से छोटी वस्तुओं को जोड़ें। डिब्बों की संख्या हैः रन-टाइम अंदर है। अब, यदि हम k = 2 और g = 1/FOPT (I) चुनते हैं, तो हमें मिलता हैः, और इसलिएः, तो डिब्बे की कुल संख्या में है। रन-टाइम है। एक ही एल्गोरिथ्म का उपयोग सटीकता के साथ रन-टाइम को ट्रेड-ऑफ करने के लिए विभिन्न मापदंडों के साथ किया जा सकता है। कुछ मापदंडों के लिए, और चुनें। फिर, पैकिंग को अधिकांश डिब्बों की आवश्यकता होती है, और रन-टाइम अंदर होता है। एल्गोरिदम 3 तीसरा एल्गोरिदम तब उपयोगी होता है जब आकार m की संख्या कम होती है (उच्च-गुणन बिन पैकिंग भी देखें)। 1-ए। सेट करें। मान लीजिए कि जी से छोटी सभी वस्तुओं को हटाकर एक उदाहरण बनाया गया है। यदि तबः 3-ए। समाकलन बाधाओं के बिना, विन्यास रैखिक कार्यक्रम का निर्माण करें। 4. एक समाधान x की गणना करें, सहिष्णुता h = 1 के साथ। परिणाम डिब्बे के साथ एक आंशिक बिन पैकिंग है। रन-टाइम है। 3-बी। के लिए एक अभिन्न समाधान के लिए x को गोल करें। आंशिक भाग के लिए डिब्बे न जोड़ें। इसके बजाय, बस पैक की गई वस्तुओं को हटा दें। एल्गोरिदम 2 के चरण 2 को शेष टुकड़ों पर चलाएँ। 1-बी। समाधान प्राप्त करने के लिए जी से छोटी वस्तुओं को जोड़ें। डिब्बों की संख्या हैः यह अधिकांश डिब्बों में उपयोग करता है, और रन-टाइम अंदर है। सुधार बेहतर अनुमान प्रदान करने के लिए केके तकनीकों में बाद में सुधार किया गया। रोथवोस एल्गोरिथम 2 के समान योजना का उपयोग करता है, लेकिन चरण 2 में एक अलग गोल प्रक्रिया के साथ। उन्होंने एक "ग्लूइंग" कदम पेश किया, जिसमें छोटी वस्तुओं को एक साथ चिपकाया जाता है ताकि एक बड़ी वस्तु मिल सके। इस ग्लूइंग का उपयोग सबसे छोटी वस्तु के आकार को लगभग बढ़ाने के लिए किया जा सकता है। जब सभी आकार कम से कम होते हैं, तो हम एल्गोरिथम 2 की गारंटी में प्रतिस्थापित कर सकते हैं, और प्राप्त कर सकते हैंः, जो एक डिब्बे देता है। होबर्ग और रोथवोस एक समान योजना का उपयोग करते हैं जिसमें वस्तुओं को पहले "पात्रों" में पैक किया जाता है, और फिर पात्रों को डिब्बे में पैक किया जाता है। उनके एल्गोरिदम को अधिकांश डिब्बे की आवश्यकता होती है। संदर्भ बिन पैकिंग