बिन पैकिंग की समस्या: Difference between revisions

Latest revision as of 15:12, 30 August 2023

बिन पैकिंग समस्या^[1]^[2]^[3]^[4] एक अनुकूलन समस्या है, जिसमें विभिन्न आकार की वस्तुओं को सीमित संख्या में बिन में पैक किया जाना चाहिए या प्रत्येक निश्चित क्षमता के कंटेनर, इस तरह से कि उपयोग किए गए बिन की संख्या कम से कम हो। समस्या जैसे कंटेनर भरना, वजन क्षमता की कमी वाले ट्रकों को लोड करना, मीडिया में फ़ाइल बैकअप बनाना और एफपीजीए अर्धचालक चिप डिजाइन में प्रौद्योगिकी मैपिंग के कई अनुप्रयोग हैं।

कम्प्यूटेशनल रूप से, समस्या एनपी-हार्ड है, और संबंधित निर्णय समस्या - यह तय करना कि क्या वस्तुएं निर्दिष्ट संख्या में बिन में फिट हो सकती हैं -एनपी-कम्पलीट है। इसकी सबसे निकृष्ट स्थिति के बावजूद, समस्या के बहुत बड़े उदाहरणों के लिए इष्टतम समाधान रिफाइंड एल्गोरिदम के साथ उत्पादित किए जा सकते हैं। इसके अतिरिक्त, अनेक सन्निकटन एल्गोरिदम उपस्थित हैं। उदाहरण के लिए, पहला फ़िट एल्गोरिथ्म तेज़ लेकिन प्रायः गैर-इष्टतम समाधान प्रदान करता है, जिसमें प्रत्येक वस्तु को पहले बिन में रखना सम्मिलित होता है जिसमें वह फिट होगा। इसके लिए Θ(n log n) समय की आवश्यकता होती है, जहां n पैक किए जाने वाले वस्तु की संख्या है। वस्तुओं की सूची को पहले घटते क्रम में क्रमबद्ध करके एल्गोरिदम को और अधिक प्रभावी बनाया जा सकता है (कभी-कभी इसे प्रथम-फिट घटते एल्गोरिदम के रूप में जाना जाता है), हालाँकि यह अभी भी एक इष्टतम समाधान की गारंटी नहीं देता है और लंबी सूचियों के लिए एल्गोरिदम के चलने के समय में वृद्धि हो सकती है। हालाँकि, यह ज्ञात है कि वस्तुओं का कम से कम ऑर्डर हमेशा उपस्थित रहता है जो फर्स्ट-फ़िट को इष्टतम समाधान तैयार करने की अनुमति देता है।^[5]

इस समस्या के कई रूप हैं, जैसे 2D पैकिंग, रैखिक पैकिंग, वजन के हिसाब से पैकिंग, लागत के हिसाब से पैकिंग, इत्यादि। बिन पैकिंग की समस्या को स्टॉक में कटौती की समस्या के एक विशेष स्थिति के रूप में भी देखा जा सकता है। जब बिन की संख्या 1 तक सीमित होती है और प्रत्येक वस्तु की मात्रा और मूल्य दोनों की विशेषता होती है, तो बिन में फिट होने वाली वस्तुओं के मूल्य को अधिकतम करने की समस्या को नैपसैक समस्या के रूप में जाना जाता है।

बिन पैकिंग का एक प्रकार जो व्यवहार में आता है वह तब होता है जब वस्तुओं को बिन में पैक करने पर स्थान साझा किया जा सकता है। विशेष रूप से, वस्तुओं का समुच्चय अपने अलग-अलग आकारों के योग की तुलना में साथ पैक किए जाने पर कम जगह घेर सकता है। इस प्रकार को वीएम पैकिंग के रूप में जाना जाता है^[6] क्योंकि जब वर्चुअल मशीन (VM) को सर्वर में पैक किया जाता है, तो वीएम द्वारा साझा किए गए पृष्ठों के कारण उनकी कुल मेमोरी आवश्यकता कम हो सकती है, जिन्हें केवल बार संग्रहीत करने की आवश्यकता होती है। यदि वस्तुएँ मनमाने ढंग से स्थान साझा कर सकती हैं, तो बिन पैकिंग की समस्या का अनुमान लगाना भी कठिन है। हालाँकि, यदि स्पेस शेयरिंग पदानुक्रम में फिट होती है, जैसा कि वर्चुअल मशीनों में मेमोरी शेयरिंग के स्थिति में है, तो बिन पैकिंग समस्या का कुशलतापूर्वक अनुमान लगाया जा सकता है।

व्यवहार में रुचि रखने वाली बिन पैकिंग का अन्य प्रकार तथाकथित ऑनलाइन बिन पैकिंग है। यहां अलग-अलग मात्रा की वस्तुओं को क्रमिक रूप से आना चाहिए, और निर्णय निर्माता को यह तय करना होगा कि वर्तमान में देखी गई वस्तु को चुनना और पैक करना है या फिर उसे पास कर देना है। प्रत्येक निर्णय बिना किसी स्मरण के होता है। इसके विपरीत, ऑफ़लाइन बिन पैकिंग अतिरिक्त वस्तु आने पर बेहतर पैकिंग प्राप्त करने की आशा में वस्तुओं को पुनर्व्यवस्थित करने की अनुमति देती है। बेशक, पुनर्व्यवस्थित की जाने वाली वस्तुओं को रखने के लिए अतिरिक्त भंडारण की आवश्यकता होती है।

औपचारिक कथन

कंप्यूटर और इंट्रैक्टेबिलिटी में^[7]^: 226 गैरी और जॉनसन ने संदर्भ [SR1] के तहत बिन पैकिंग समस्या को सूचीबद्ध किया है। वे इसके निर्णय प्रकार को निम्नानुसार परिभाषित करते हैं।

उदाहरण: परिमित समुच्चय $I$ वस्तुओं का, आकार $s(i)\in \mathbb {Z} ^{+}$ प्रत्येक के लिए $i\in I$ , धनात्मक पूर्णांक बिन क्षमता $B$ , और धनात्मक पूर्णांक $K$ .

प्रश्न: क्या इसका कोई विभाजन है? $I$ असंयुक्त समुच्चय में $I_{1},\dots ,I_{K}$ इस प्रकार कि प्रत्येक में वस्तु के आकार का योग $I_{j}$ $B$ या कम है?

ध्यान दें कि साहित्य में प्रायः समकक्ष संकेतन का उपयोग किया जाता है, जहां $B=1$ और $s(i)\in \mathbb {Q} \cap (0,1]$ प्रत्येक के लिए $i\in I$ . इसके अलावा, अनुसंधान ज्यादातर अनुकूलन संस्करण में रुचि रखता है, जो न्यूनतम संभव मूल्य मांगता है $K$ . कोई समाधान इष्टतम होता है यदि उसमें न्यूनतम हो $K$ . $K$ वें-वस्तुओं के समुच्चय के लिए इष्टतम समाधान के लिए मूल्य $I$ द्वारा निरूपित किया जाता है $\mathrm {OPT} (I)$ या केवल $\mathrm {OPT}$ यदि मदों का समुच्चय संदर्भ से स्पष्ट है।

समस्या का संभावित पूर्णांक प्रोग्रामिंग सूत्रीकरण है:

minimize $K=\sum _{j=1}^{n}y_{j}$
subject to	$K\geq 1,$
	$\sum _{i\in I}s(i)x_{ij}\leq By_{j},$	$\forall j\in \{1,\ldots ,n\}$
	$\sum _{j=1}^{n}x_{ij}=1,$	$\forall i\in I$
	$y_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$
	$x_{ij}\in \{0,1\},$	$\forall i\in I\,\forall j\in \{1,\ldots ,n\}$

जहाँ $y_{j}=1$ अगर वहां था $j$ प्रयोग किया जाता है और $x_{ij}=1$ यदि वस्तु $i$ बिन $j$ में डाल दिया जाता है^[8]

बिन पैकिंग की कठोरता

बिन पैकिंग समस्या सशक्त NP-पूर्णता दृढ़तापूर्वक एनपी-पूर्णता है। इसे बिन पैकिंग में एनपी-कम्पलीट 3-विभाजन समस्या को कम करके सिद्ध किया जा सकता है।^[7]

इसके अलावा, पूर्ण सन्निकटन अनुपात से छोटा कोई सन्निकटन एल्गोरिदम नहीं हो सकता है ${\tfrac {3}{2}}$ जब तक ${\mathsf {P}}={\mathsf {NP}}$ . इसे विभाजन समस्या को कम करके सिद्ध किया जा सकता है:^[9] विभाजन का एक उदाहरण दिया गया है जहां सभी इनपुट संख्याओं का योग $2T$ है, बिन-पैकिंग का एक उदाहरण बनाएं जिसमें बिन का आकार हो $T$ . यदि इनपुट का समान विभाजन उपस्थित है, तो इष्टतम पैकिंग के लिए 2 बिन की आवश्यकता होती है; इसलिए, प्रत्येक एल्गोरिदम का सन्निकटन अनुपात इससे छोटा होता है 3/2 को 3 बिन से कम लौटाना होगा, जो कि 2 बिन होने चाहिए। इसके विपरीत, यदि इनपुट का कोई समान विभाजन नहीं है, तो इष्टतम पैकिंग के लिए कम से कम 3 बिन की आवश्यकता होती है।

दूसरी ओर, बिन पैकिंग किसी भी निश्चित संख्या में बिन के लिए छद्म-बहुपद समय में हल करने योग्य है $K$ , और किसी भी निश्चित बिन क्षमता $B$ के लिए बहुपद समय में हल करने योग्य है।^[7]

बिन पैकिंग के लिए अनुमान एल्गोरिदम

सन्निकटन एल्गोरिदम के प्रदर्शन को मापने के लिए साहित्य में दो सन्निकटन अनुपातों पर विचार किया गया है। वस्तुओं की दी गई सूची के लिए $L$ जो नंबर $A(L)$ एल्गोरिथ्म के दौरान उपयोग किए गए बिन की संख्या को दर्शाता है $A$ सूची में लागू किया जाता है $L$ , जबकि $\mathrm {OPT} (L)$ इस सूची के लिए इष्टतम संख्या को दर्शाता है। सबसे निकृष्ट स्थिति वाला प्रदर्शन अनुपात $R_{A}$ एक एल्गोरिदम के लिए $A$ परिभाषित किया जाता है।

R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.

दूसरी ओर, स्पर्शोन्मुख सबसे निकृष्ट स्थिति का अनुपात $R_{A}^{\infty }$ परिभाषित किया जाता है।

R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.

समान रूप से, $R_{A}^{\infty }$ सबसे छोटी संख्या है जैसे कि कुछ स्थिरांक K उपस्थित है, जैसे कि सभी सूचियों के लिए L:'^[4]:

$A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K$ .

इसके अतिरिक्त, कोई भी सूचियों को उन तक सीमित कर सकता है जिनके लिए सभी वस्तुओं का आकार अधिकतम हो $\alpha$ . ऐसी सूचियों के लिए, सीमित आकार के प्रदर्शन अनुपात $R_{A}({\text{size}}\leq \alpha )$ और $R_{A}^{\infty }({\text{size}}\leq \alpha )$ को इस प्रकार दर्शाया गया है।

बिन पैकिंग के लिए अनुमान एल्गोरिदम को दो श्रेणियों में वर्गीकृत किया जा सकता है:

ऑनलाइन अनुमान, जो किसी दिए गए क्रम में वस्तुओं पर विचार करते हैं और उन्हें एक-एक करके बिन के अंदर रखते हैं। ये अनुमान इस समस्या के ऑनलाइन संस्करण पर भी लागू होते हैं।
ऑफ़लाइन आंकड़े, जो दी गई वस्तुओं की सूची को संशोधित करते हैं, उदा. वस्तुओं को आकार के अनुसार क्रमबद्ध करके। ये एल्गोरिदम अब इस समस्या के ऑनलाइन संस्करण पर लागू नहीं हैं। हालाँकि, उनकी छोटी समय-जटिलता के लाभ को बनाए रखते हुए उनके पास बेहतर सन्निकटन गारंटी है। ऑफ़लाइन अनुमानों की उप-श्रेणी स्पर्शोन्मुख सन्निकटन योजनाएँ हैं। इन एल्गोरिदम में फॉर्म की अनुमानित गारंटी होती है $(1+\varepsilon )\mathrm {OPT} (L)+C$ कुछ स्थिरांक के लिए जिस पर निर्भर हो सकता है $1/\varepsilon$ . मनमाने ढंग से बड़े के लिए $\mathrm {OPT} (L)$ ये एल्गोरिदम मनमाने ढंग से करीब आ जाते हैं $\mathrm {OPT} (L)$ . हालाँकि, यह अनुमानी दृष्टिकोण की तुलना में (काफी) बढ़ी हुई समय जटिलता की कीमत पर आता है।

ऑनलाइन अनुमान

बिन पैकिंग समस्या के ऑनलाइन संस्करण में, आइटम के बाद एक आते हैं और किसी आइटम को कहां रखा जाए इसका (अपरिवर्तनीय) निर्णय अगला आइटम जानने से पहले करना पड़ता है या यहां तक कि कोई दूसरा आइटम होगा भी या नहीं। डेविड एस. जॉनसन द्वारा अपनी पीएचडी थीसिस में बिन-पैकिंग के लिए ऑफ़लाइन और ऑनलाइन अनुमानों के विविध सेट का अध्ययन किया गया है।^[10]

सिंगल-क्लास एल्गोरिदम

ऐसे कई सरल एल्गोरिदम हैं जो निम्नलिखित सामान्य योजना का उपयोग करते हैं:

इनपुट सूची में प्रत्येक वस्तु के लिए:
1. यदि वस्तु वर्तमान में ओपन बिन में फिट होती है, तो उसे इनमें से किसी एक बिन में डाल दें;
2. अन्यथा, नया बिन ओपन करें और उसमें नई वस्तु डालें।

एल्गोरिदम उस मानदंड में भिन्न होते हैं जिसके द्वारा वे चरण 1 में नए वस्तु के लिए ओपन बिन का चयन करते हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

नेक्स्ट-फिट (NF) हमेशा एकओपन बिन रखता है। जब नई वस्तु इसमें फिट नहीं होती है, तो यह वर्तमान बिन को बंद कर देता है और एक नया बिन खोलता है। इसका लाभ यह है कि यह एक बाउंडेड-स्पेस एल्गोरिदम है क्योंकि इसे मेमोरी में केवल एक ओपन बिन रखने की आवश्यकता होती है। इसका नुकसान यह है कि इसका स्पर्शोन्मुख सन्निकटन अनुपात 2 है। विशेष रूप से, $NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$ , और प्रत्येक के लिए $N\in \mathbb {N}$ वहाँ एक सूची उपस्थित है $L$ ऐसा है कि $\mathrm {OPT} (L)=N$ और $NF(L)=2\cdot \mathrm {OPT} (L)-2$ .^[10]वस्तु के आकार के आधार पर इसके स्पर्शोन्मुख सन्निकटन अनुपात में कुछ हद तक सुधार किया जा सकता है: $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2$ सभी के लिए $\alpha \geq 1/2$ और $R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )$ सभी के लिए $\alpha \leq 1/2$ . प्रत्येक एल्गोरिदम के लिए $A$ यह एक एनीफिट-एल्गोरिदम है जो इसे धारण करता है $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )$ .
नेक्स्ट-के-फिट (NkF) नेक्स्ट-फिट का एक प्रकार है, लेकिन एल्गोरिदम केवल एक बिन को ओपन रखने के बजाय आखिरी को रखता है। $k$ बिन खुलते हैं और पहला बिन चुनते हैं जिसमें वस्तु फिट होती है। इसलिए, इसे k-बाउंडेड स्पेस एल्गोरिथम कहा जाता है।^[11] के लिए $k\geq 2$ एनकेएफ ऐसे परिणाम देता है जो NF के परिणामों की तुलना में बेहतर होते हैं, हालांकि, बढ़ रहे हैं $k$ से बड़े स्थिर मानों के लिए $2$ अपने सबसे निकृष्ट स्थिति वाले व्यवहार में एल्गोरिदम को और बेहतर नहीं बनाता है। यदि एल्गोरिदम $A$ एक ऑलमोस्टएनीफिट-एल्गोरिदम है और $m=\lfloor 1/\alpha \rfloor \geq 2$ तब $R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m$ .^[10]
फर्स्ट-फिट (FF) सभी बिन को उसी क्रम में ओपन रखता है, जिस क्रम में वे ओपन किये गए थे। यह प्रत्येक नई वस्तु को पहले बिन में रखने का प्रयास करता है जिसमें वह फिट होती है। इसका सन्निकटन अनुपात है $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ , और इनपुट सूचियों का एक परिवार है $L$ जिसके लिए $FF(L)$ इस सीमा से मेल खाता है।^[12]
बेस्ट-फिट (BF), भी, सभी बिन ओपन रखता है, लेकिन प्रत्येक नए वस्तु को अधिकतम लोड के साथ बिन में रखने का प्रयास करता है जिसमें वह फिट बैठता है। इसका सन्निकटन अनुपात FF के समान है, अर्थात: $BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ , और इनपुट सूचियों का एक परिवार है $L$ जिसके लिए $BF(L)$ इस सीमा से मेल खाता है.^[13]
वर्स्ट-फिट (डब्ल्यूएफ) प्रत्येक नई वस्तु को न्यूनतम लोड के साथ बिन में रखने का प्रयास करता है। यह नेक्स्ट-फ़िट जितना बुरा व्यवहार कर सकता है, और उसके लिए सबसे निकृष्ट स्थिति वाली सूची में ऐसा करेगा $NF(L)=2\cdot \mathrm {OPT} (L)-2$ . इसके अलावा, यह ऐसा मानता है $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$ . चूँकि WF एक एनीफिट-एल्गोरिदम है, इसलिए ऐसा एनीफिट-एल्गोरिदम उपस्थित है $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$ .^[10]
ऑलमोस्ट वर्स्ट-फिट (AWF) प्रत्येक नई वस्तु को दूसरे सबसे ओपन ओपन बिन (या यदि ऐसे दो बिन हैं तो सबसे ओपन बिन) के अंदर रखने का प्रयास करता है। यदि यह फिट नहीं होता है, तो यह सबसे ओपन प्रयास करता है। इसका स्पर्शोन्मुख सबसे निकृष्ट स्थिति का अनुपात है ${\tfrac {17}{10}}$ .^[10]इन परिणामों को सामान्यीकृत करने के लिए, जॉनसन ने ऑनलाइन हेयुरिस्टिक्स के दो वर्ग पेश किए जिन्हें एनी-फिट एल्गोरिदम और ऑलमोस्ट-एनी-फिट एल्गोरिदम कहा जाता है:'^[4]^: 470
एनीफिट (AF) एल्गोरिथम में, यदि वर्तमान गैर-रिक्त बिन B₁,...,B_j हैं, तो वर्तमान वस्तु को B_j₊₁ में पैक नहीं किया जाएगा जब तक कि यह B₁,...,B_j. में से किसी में फिट न हो. FF, WF, BFऔर AWF एल्गोरिदम इस शर्त को पूरा करते हैं। जॉनसन ने किसी भी एनीफिट एल्गोरिथम A और किसी के लिए भी यह साबित कर दिया $\alpha$ :
$R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )$ .
ऑलमोस्टएनीफिट (एएएफ) एल्गोरिदम में, यदि वर्तमान गैर-रिक्त बिन B₁,...,B_j, हैं, और इन बिन में से, B_k सबसे छोटे भार वाला अद्वितीय बिन है, तो वर्तमान वस्तु को B_k में पैक नहीं किया जाएगा जब तक कि वह अपनी बाईं ओर के किसी भी बिन में फिट न हो जाए। FF, BF और AWF एल्गोरिदम इस शर्त को पूरा करते हैं, लेकिन WF नहीं करता है। जॉनसन ने यह साबित किया, किसी भी AAF एल्गोरिदम A और किसी $α$ के लिए :
$R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )$ विशेष रूप से: $R_{A}^{\infty }=1.7$ .

रिफाइंड एल्गोरिदम

उन अनुमानों के साथ बेहतर सन्निकटन अनुपात संभव है जो एनीफिट नहीं हैं। ये अनुमान सामान्यतः विभिन्न आकार श्रेणियों की वस्तुओं के लिए समर्पित ओपन बिन के कई वर्ग रखते हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

रिफाइंड-फर्स्ट-फिट बिन पैकिंग (आरएफएफ) वस्तु के आकार को चार श्रेणियों में विभाजित करता है: $\left({\frac {1}{2}},1\right]$ , $\left({\frac {2}{5}},{\frac {1}{2}}\right]$ , $\left({\frac {1}{3}},{\frac {2}{5}}\right]$ , और $\left(0,{\frac {1}{3}}\right]$ . इसी प्रकार, बिन को चार वर्गों में वर्गीकृत किया गया है। अगला वस्तु $i\in L$ सबसे पहले इसके संबंधित वर्ग को सौंपा गया है। उस वर्ग के अंदर, इसे फर्स्ट-फिट बिन पैकिंग|फर्स्ट-फिट का उपयोग करके एक बिन को सौंपा गया है। ध्यान दें कि यह एल्गोरिदम कोई भी-फिट एल्गोरिदम नहीं है क्योंकि यह इस तथ्य के बावजूद एक नया बिन खोल सकता है कि वर्तमान वस्तु एक ओपन बिन के अंदर फिट बैठता है। यह एल्गोरिदम सबसे पहले एंड्रयू ची-चिह याओ द्वारा प्रस्तुत किया गया था,^[14] जिसने साबित कर दिया कि इसकी अनुमानित गारंटी है $RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ और सूचियों का एक परिवार प्रस्तुत किया $L_{k}$ साथ $RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3$ के लिए $\mathrm {OPT} (L)=6k+1$ .
हार्मोनिक-के आकार के अंतराल को विभाजित करता है $(0,1]$ एक हार्मोनिक प्रगति (गणित) पर आधारित $k-1$ टुकड़े $I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]$ के लिए $1\leq j<k$ और $I_{k}:=\left(0,{\frac {1}{k}}\right]$ ऐसा है कि $\bigcup _{j=1}^{k}I_{j}=(0,1]$ . इस एल्गोरिथम का वर्णन सबसे पहले ली और ली द्वारा किया गया था।^[15] इसमें समय की जटिलता है ${\mathcal {O}}(|L|\log(|L|))$ और प्रत्येक चरण पर, अधिकतम होते हैं $k$ ओपन बिन जिनका उपयोग संभावित रूप से वस्तुओं को रखने के लिए किया जा सकता है, यानी, यह एक है $k$ -बाउंडेड स्पेस एल्गोरिदम। के लिए $k\rightarrow \infty$ , इसका सन्निकटन अनुपात संतुष्ट करता है $R_{Hk}^{\infty }\approx 1.6910$ , और यह स्पर्शोन्मुख रूप से तंग है।
रिफाइंड-हार्मोनिक, हार्मोनिक-के के विचारों को रिफाइंड फर्स्ट-फिट बिन पैकिंग|रिफाइंड-फर्स्ट-फिट के विचारों के साथ जोड़ता है। यह वस्तुओं को इससे बड़ा रखता है ${\tfrac {1}{3}}$ रिफाइंड-फर्स्ट-फ़िट के समान, जबकि छोटी वस्तुओं को हार्मोनिक-के का उपयोग करके रखा जाता है। इस रणनीति का उद्देश्य उन बिन के लिए भारी अपशिष्ट को कम करना है जिनमें बड़े टुकड़े होते हैं ${\tfrac {1}{2}}$ . इस एल्गोरिथम का वर्णन सबसे पहले ली और ली द्वारा किया गया था।^[15] उन्होंने ये बात साबित कर दी $k=20$ यह उसे धारण करता है $R_{RH}^{\infty }\leq 373/228$ .

ऑनलाइन एल्गोरिदम के लिए सामान्य निचली सीमाएं

याओ^[14]1980 में साबित हुआ कि एसिम्प्टोटिक प्रतिस्पर्धी अनुपात से छोटा कोई ऑनलाइन एल्गोरिदम नहीं हो सकता है ${\tfrac {3}{2}}$ . भूरा^[16] और लिआंग^[17] इस बाध्यता में सुधार हुआ 1.53635. बाद में, इस सीमा में सुधार किया गया 1.54014 Vliet द्वारा.^[18] 2012 में, बेकेसी और गैलाम्बोस द्वारा इस निचली सीमा में फिर से सुधार किया गया^[19] ${\tfrac {248}{161}}\approx 1.54037$ है

तुलना तालिका

एल्गोरिदम	अनुमान की गारंटी	निकृष्ट सूची $L$	समय जटिलता
नेक्स्ट-फ़िट (एनएफ)	$NF(L)\leq 2\cdot \mathrm {OPT} (L)-1$ ^[10]	$NF(L)=2\cdot \mathrm {OPT} (L)-2$ ^[10]	${\mathcal {O}}(\|L\|)$
फर्स्ट-फिट (एफएफ)	$FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$ ^[12]	$FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$ ^[12]	${\mathcal {O}}(\|L\|\log(\|L\|))$ ^[10]
बेस्ट-फिट (बीएफ)	$BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor$ ^[13]	$BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor$ ^[13]	${\mathcal {O}}(\|L\|\log(\|L\|))$ ^[10]
Worst-Fit (WF)	$WF(L)\leq 2\cdot \mathrm {OPT} (L)-1$ ^[10]	$WF(L)=2\cdot \mathrm {OPT} (L)-2$ ^[10]	${\mathcal {O}}(\|L\|\log(\|L\|))$ ^[10]
ऑलमोस्ट-वर्स्ट-फिट (एडब्लूएफ)	$R_{AWF}^{\infty }\leq 17/10$ ^[10]	$R_{AWF}^{\infty }=17/10$ ^[10]	${\mathcal {O}}(\|L\|\log(\|L\|))$ ^[10]
रिफाइंड-फर्स्ट-फिट (आरएफएफ)	$RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5$ ^[14]	$RFF(L)=(5/3)\mathrm {OPT} (L)+1/3$ (for $\mathrm {OPT} (L)=6k+1$ )^[14]	${\mathcal {O}}(\|L\|\log(\|L\|))$ ^[14]
हार्मोनिक-के (एचके)	$R_{Hk}^{\infty }\leq 1.69103$ for $k\rightarrow \infty$ ^[15]	$R_{Hk}^{\infty }\geq 1.69103$ ^[15]	${\mathcal {O}}(\|L\|\log(\|L\|)$ ^[15]
रिफाइंड हार्मोनिक (आरएच)	$R_{RH}^{\infty }\leq 373/228\approx 1.63597$ ^[15]		${\mathcal {O}}(\|L\|)$ ^[15]
मॉडिफाइड हार्मोनिक (MH)	$R_{MH}^{\infty }\leq 538/33\approx 1.61562$ ^[20]
मॉडिफाइड हार्मोनिक 2 (MH2)	$R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217$ ^[20]
हार्मोनिक + 1 (H+1)		$R_{H+1}^{\infty }\geq 1.59217$ ^[21]
हार्मोनिक ++ (H++)	$R_{H++}^{\infty }\leq 1.58889$ ^[21]	$R_{H++}^{\infty }\geq 1.58333$ ^[21]

ऑफ़लाइन एल्गोरिदम

बिन पैकिंग के ऑफ़लाइन संस्करण में, एल्गोरिदम सभी वस्तुओं को बिन में रखना प्रारम्भ करने से पहले देख सकता है। यह बेहतर सन्निकटन अनुपात प्राप्त करने की अनुमति देता है।

गुणात्मक सन्निकटन

ऑफ़लाइन एल्गोरिदम द्वारा प्रयुक्त सबसे सरल तकनीक है:

घटते आकार के अनुसार इनपुट सूची को क्रमित करना।
आदेशित सूची पर एक ऑनलाइन एल्गोरिदम चलाएँ।

जॉनसन^[10] ने साबित किया कि कोई भी ऐनीफिट एल्गोरिदम A जो घटते आकार के आधार पर क्रमित सूची पर चलता है, उसमें एक स्पर्शोन्मुख सन्निकटन अनुपात होता है।

$1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25$ .इस परिवार में कुछ एल्गोरिदम हैं (अधिक जानकारी के लिए लिंक किए गए पेज देखें):

फर्स्ट-फिट-डिक्रीजिंग (एफएफडी) - वस्तु को घटते आकार के आधार पर ऑर्डर करता है, फिर फर्स्ट-फिट को कॉल करता है। इसका सन्निकटन अनुपात $FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$ है, और यह तंग है।^[22]
नेक्स्ट-फिट-डिक्रीजिंग (एनएफडी) - वस्तुओं को घटते आकार के आधार पर ऑर्डर करता है, फिर नेक्स्ट-फिट बिन पैकिंग|नेक्स्ट-फिट को कॉल करता है। इसका अनुमानित अनुपात सबसे निकृष्ट स्थिति में 1.7 से थोड़ा कम है।^[23] इसका संभाव्य विश्लेषण भी किया गया है।^[24] नेक्स्ट-फ़िट एक सूची और उसके व्युत्क्रम को समान संख्या में बिन में पैक करता है। इसलिए, नेक्स्ट-फिट-इंक्रीजिंग का प्रदर्शन नेक्स्ट-फिट-डिक्रीजिंग के समान ही है।^[25]
संशोधित फर्स्ट-फिट-डिक्रीजिंग (एमएफएफडी)^[26]- आकार के आधार पर वस्तुओं को बड़े, मध्यम, छोटे और छोटे आकार के चार वर्गों में वर्गीकृत करके आधे बिन से बड़ी वस्तुओं के लिए एफएफडी में सुधार किया जाता है, क्रमशः> 1/2 बिन,> 1/3 बिन,> 1/6 बिन और छोटे आकार वाली वस्तुओं के अनुरूप इसकी सन्निकटन गारंटी $MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$ .है।^[27]

फर्नांडीज डे ला वेगा और ल्यूकेर^[28] बिन पैकिंग के लिए एक बहुपद-समय सन्निकटन योजना प्रस्तुत की। हरएक के लिए $\varepsilon >0$ , उनका एल्गोरिदम अधिकतम आकार के साथ एक समाधान ढूंढता है $(1+\varepsilon )\mathrm {OPT} +1$ और समय पर चलता है ${\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)$ , जहाँ ${\mathcal {O}}_{\varepsilon }(1)$ किसी फ़ंक्शन को केवल उस पर निर्भर दर्शाता है $1/\varepsilon$ . इस एल्गोरिदम के लिए, उन्होंने अनुकूली इनपुट राउंडिंग की विधि का आविष्कार किया: इनपुट संख्याओं को समूहीकृत किया जाता है और प्रत्येक समूह में अधिकतम मूल्य तक पूर्णांकित किया जाता है। यह विभिन्न आकारों की एक छोटी संख्या के साथ एक उदाहरण उत्पन्न करता है, जिसे विन्यास रैखिक कार्यक्रम का उपयोग करके बिल्कुल हल किया जा सकता है।^[29]

योगात्मक सन्निकटन

करमरकर-कार्प बिन पैकिंग एल्गोरिदम अधिकतम आकार के साथ समाधान $\mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))$ ढूंढता है, और समय बहुपद $n$ में चलता है (बहुपद की डिग्री उच्च होती है - कम से कम 8)।

रोथवॉस^[30] एल्गोरिदम प्रस्तुत किया जो अधिक से अधिक समाधान $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))$ बिन उत्पन्न करता है।

होबर्ग और रोथवॉस^[31] अधिक से अधिक समाधान उत्पन्न करने के लिए इस एल्गोरिथम में सुधार किया गया $\mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))$ बिन. एल्गोरिथ्म यादृच्छिक है, और इसका रनिंग-टाइम $n$ बहुपद है।

तुलना तालिका

एल्गोरिदम	अनुमान की गारंटी	निकृष्ट स्थिति का उदाहरण
फर्स्ट-फिट-डिक्रीजिंग (एफएफडी)	$\mathrm {FFD} (I)\leq {\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$ ^[22]	$\mathrm {FFD} (I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}$ ^[22]
संशोधित-प्रथम-फिट-घटती (एमएफएफडी)	$\mathrm {MFFD} (I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1$ ^[27]	$R_{\mathrm {MFFD} }^{\infty }\geq {\frac {71}{60}}$ ^[26]
करमरकर और कार्प	$\mathrm {KK} (I)\leq \mathrm {OPT} (I)+O(\log ^{2}{\mathrm {OPT} (I)})$ ^[32]
रोथवॉस	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)}\log \log {\mathrm {OPT} (I)})$ ^[30]
होबर्ग और रोथवॉस	$\mathrm {HB} (I)\leq \mathrm {OPT} (I)+O(\log {\mathrm {OPT} (I)})$ ^[31]

सटीक एल्गोरिदम

मार्टेलो और टोथ^[33] 1-आयामी बिन-पैकिंग समस्या के लिए एक सटीक एल्गोरिदम विकसित किया, जिसे एमटीपी कहा जाता है। एक तेज़ विकल्प 2002 में कोर्फ द्वारा प्रस्तावित बिन कंप्लीशन एल्गोरिदम^[34] और बाद में सुधार हुआ है^[35]

2013 में श्रेइबर और कोर्फ द्वारा एक और सुधार प्रस्तुत किया गया।^[36] नए बेहतर बिन कंप्लीशन एल्गोरिदम को 100 वस्तुओं के साथ गैर-तुच्छ समस्याओं पर बिन कंप्लीशन की तुलना में परिमाण के पांच ऑर्डर तक तेज दिखाया गया है, और इष्टतम समाधान के रूप में 20 बिन से कम वाली समस्याओं पर बेलोव और शेइथाउर द्वारा बीसीपी (ब्रांच-एंड-कट-एंड-प्राइस) एल्गोरिदम से बेहतर प्रदर्शन करता है। कौन सा एल्गोरिदम सबसे अच्छा प्रदर्शन करता है यह समस्या के गुणों जैसे वस्तुओं की संख्या, बिन की इष्टतम संख्या, इष्टतम समाधान में अप्रयुक्त स्थान और मूल्य परिशुद्धता पर निर्भर करता है।

विभिन्न आकारों की छोटी संख्या

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

विखंडन के साथ बिन-पैकिंग

विखंडन या खंडित वस्तु बिन-पैकिंग के साथ बिन-पैकिंग बिन पैकिंग समस्या का एक प्रकार है जिसमें वस्तुओं को भागों में तोड़ने और प्रत्येक भाग को अलग-अलग बिन पर अलग से रखने की अनुमति होती है। वस्तुओं को भागों में तोड़ने से समग्र प्रदर्शन में सुधार हो सकता है, उदाहरण के लिए, कुल बिन की संख्या को कम करना। इसके अलावा, इष्टतम शेड्यूल खोजने की कम्प्यूटेशनल समस्या आसान हो सकती है, क्योंकि कुछ अनुकूलन चर निरंतर हो जाते हैं। दूसरी ओर, वस्तुओं को अलग करना महंगा पड़ सकता है। यह समस्या सबसे पहले मंडल, चक्रवर्ती और घोष द्वारा प्रस्तुत की गई थी।^[37]

वेरिएंट

समस्या के दो मुख्य रूप हैं.

पहले संस्करण में, जिसे आकार-बढ़ती विखंडन ((BP-SIF)) के साथ बिन-पैकिंग कहा जाता है, प्रत्येक वस्तु खंडित हो सकता है; प्रत्येक टुकड़े के आकार में ओवरहेड इकाइयाँ जोड़ी जाती हैं।
दूसरे संस्करण में, जिसे आकार-संरक्षण विखंडन ((BP-SIF)) के साथ बिन-पैकिंग कहा जाता है, प्रत्येक वस्तु का एक आकार और एक लागत होती है; किसी वस्तु को खंडित करने से उसकी लागत बढ़ जाती है लेकिन उसका आकार नहीं बदलता।

कम्प्यूटेशनल जटिलता

मंडल, चक्रवर्ती और घोष^[37]साबित हुआ कि (BP-SIF) एनपी-हार्ड है।

मेनकेरमैन और रोम^[38] पता चला कि (BP-SIF) और (BP-SIF) दोनों दृढ़ता से एनपी-हार्ड हैं। कठोरता के बावजूद, वे कई एल्गोरिदम प्रस्तुत करते हैं और उनके प्रदर्शन की जांच करते हैं। उनके एल्गोरिदम बिन-पैकिंग के लिए क्लासिक एल्गोरिदम का उपयोग करते हैं, जैसे नेक्स्ट-फिट बिन पैकिंग|नेक्स्ट-फिट और फर्स्ट-फिट-डिक्रीजिंग बिन पैकिंग|फर्स्ट-फिट डिक्रीजिंग, उनके एल्गोरिदम के आधार के रूप में।

बर्टाज़ी, गोल्डन और वांग^[39] के साथ BP-SIF का एक संस्करण पेश किया $1-x$ विभाजन नियम: किसी वस्तु को उसके आकार के अनुसार केवल एक ही तरीके से विभाजित करने की अनुमति है। उदाहरण के लिए, यह वाहन रूटिंग समस्या के लिए उपयोगी है। अपने पेपर में, वे वेरिएंट का सबसे निकृष्ट प्रदर्शन प्रदान करते हैं।

शचनाई, तामीर और येहेज़केली^[40] (BP-SIF) और (BP-SIF) के लिए विकसित सन्निकटन योजनाएं; एक दोहरी बहुपद-समय सन्निकटन योजना (समस्या के दोहरे संस्करण के लिए एक पीटीएएस), एक एसिम्प्टोटिक पीटीएएस जिसे एपीटीएएस कहा जाता है, और एक दोहरी एसिम्प्टोटिक fptas जिसे दोनों संस्करणों के लिए एएफपीटीएएस कहा जाता है।

एकिसि^[41] (BP-SIF) का एक प्रकार पेश किया गया जिसमें कुछ वस्तुएं विवादित हैं, और विवादित वस्तुओं के टुकड़ों को एक ही बिन में पैक करना मना है। उन्होंने साबित कर दिया कि यह वैरिएंट भी एनपी-हार्ड है।

कैसाज़ा और सेसेली^[42] बिना किसी लागत और बिना किसी ओवरहेड वाला एक संस्करण पेश किया गया है, और बिन की संख्या निश्चित है। हालाँकि, विखंडन की संख्या कम होनी चाहिए। वे सटीक और अनुमानित दोनों समाधानों के लिए गणितीय प्रोग्रामिंग एल्गोरिदम प्रस्तुत करते हैं।

बिन पर कार्डिनैलिटी बाधाएँ

बिन पैकिंग का एक प्रकार है जिसमें बिन पर कार्डिनैलिटी बाधाएं होती हैं: प्रत्येक बिन में कुछ निश्चित पूर्णांक k के लिए अधिकतम k वस्तु हो सकते हैं।

क्राउज़, शेन और श्वेटमैन^[44] इस समस्या को इष्टतम कार्य शेड्यूलिंग के एक प्रकार के रूप में प्रस्तुत करें: एक कंप्यूटर में कुछ k प्रोसेसर होते हैं। कुछ n नौकरियाँ ऐसी हैं जिनमें इकाई समय लगता है (1), लेकिन उनकी मेमोरी आवश्यकताएँ भिन्न होती हैं। प्रत्येक समय-इकाई को एक ही बिन माना जाता है। लक्ष्य यथासंभव कम बिन (=समय इकाइयाँ) का उपयोग करना है, जबकि यह सुनिश्चित करना है कि प्रत्येक बिन में, अधिकतम k नौकरियाँ चलती हैं। वे कई अनुमानी एल्गोरिदम प्रस्तुत करते हैं जो अधिक से अधिक समाधान ढूंढते हैं $2\mathrm {OPT}$ बिन.
केलरर और पफ़रस्की^[45] रन-टाइम के साथ एक एल्गोरिदम प्रस्तुत करें $O(n^{2}\log {n})$ , वह अधिक से अधिक समाधान ढूंढ लेता है $\left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil$ बिन. उनका एल्गोरिदम ओपीटी के लिए बाइनरी खोज करता है। प्रत्येक खोजे गए मान m के लिए, यह वस्तु को 3m/2 बिन में पैक करने का प्रयास करता है।

गैर-योगात्मक कार्य

बिन-पैकिंग मॉडल को अधिक सामान्य लागत और लोड कार्यों तक विस्तारित करने के कई तरीके हैं:

अनिली, ब्रैमल और सिम्ची-लेवी^[46] एक सेटिंग का अध्ययन करें जहां एक बिन की लागत बिन में वस्तुओं की संख्या का एक अवतल कार्य है। इसका उद्देश्य कूड़ेदानों की संख्या के बजाय कुल लागत को कम करना है। वे दिखाते हैं कि अगली-फिट-बढ़ती बिन पैकिंग अधिकतम 7/4 का पूर्णतः सबसे निकृष्ट-स्थिति सन्निकटन अनुपात प्राप्त करती है, और किसी भी अवतल और मोनोटोन लागत फ़ंक्शन के लिए 1.691 का एक एसिम्प्टोटिक सबसे निकृष्ट-स्थिति अनुपात प्राप्त करती है।
कोहेन, केलर, मिर्रोकनी और ज़दिमोघदाम^[47] ऐसी सेटिंग का अध्ययन करें जहां वस्तु का आकार पहले से ज्ञात नहीं है, लेकिन यह एक यादृच्छिक चर है। यह क्लाउड कम्प्यूटिंग वातावरण में विशेष रूप से आम है। हालाँकि एक निश्चित उपयोगकर्ता के लिए आवश्यक संसाधनों की मात्रा की ऊपरी सीमा होती है, अधिकांश उपयोगकर्ता क्षमता से बहुत कम उपयोग करते हैं। इसलिए, क्लाउड मैनेजर को थोड़ी सी स्मृति अति प्रतिबद्धता से बहुत फायदा हो सकता है। यह मौका बाधाओं के साथ बिन पैकिंग के एक प्रकार को प्रेरित करता है: प्रत्येक बिन में आकारों का योग अधिकतम B होने की संभावना कम से कम पी होनी चाहिए, जहां पी एक निश्चित स्थिरांक है (मानक बिन पैकिंग पी = 1 से मेल खाती है)। वे दिखाते हैं कि, हल्की धारणाओं के तहत, यह समस्या एक सबमॉड्यूलर बिन पैकिंग समस्या के बराबर है, जिसमें प्रत्येक बिन में लोड वस्तुओं के योग के बराबर नहीं है, बल्कि इसके एक निश्चित सबमॉड्यूलर समुच्चय फ़ंक्शन के बराबर है।

संसाधन

BPPLIB - सर्वेक्षण, कोड, बेंचमार्क, जनरेटर, सॉल्वर और ग्रंथ सूची की एक लाइब्रेरी।

कार्यान्वयन

ऑनलाइन: 1डी और 2D बिन पैकिंग के लिए अनुमानों का दृश्य
पायथन: prtpy पैकेज में विभिन्न संख्या-विभाजन, बिन-पैकिंग और बिन-कवरिंग एल्गोरिदम के लिए कोड सम्मिलित हैं। बिनपैकिंग पैकेज में दो विशिष्ट बिन पैकिंग समस्याओं को हल करने के लिए लालची एल्गोरिदम सम्मिलित हैं।^[55]
सी++: बिन-पैकिंग पैकेज में विभिन्न लालची एल्गोरिदम के साथ-साथ परीक्षण डेटा भी सम्मिलित है। OR-tools package में C++ में बिन पैकिंग एल्गोरिदम, Python, C# और Java में रैपर्स सम्मिलित हैं।
सी: परिणामों और छवियों के साथ सी में 7 क्लासिक अनुमानित बिन पैकिंग एल्गोरिदम का कार्यान्वयन
PHP: PHP क्लास किसी दिए गए आकार सीमा से अधिक के बिना फ़ाइलों को पैक करने के लिए
हास्केल: एफएफडी और एमएफएफडी सहित कई बिन पैकिंग अनुमानों का कार्यान्वयन।
सी: एफपार्ट: फाइलों को पैक करने के लिए ओपन-सोर्स कमांड-लाइन टूल (सी, बीएसडी-लाइसेंस प्राप्त)
सी#: बिन पैकिंग और कटिंग स्टॉक सॉल्वर
जावा: कैपर्फ - कटिंग और पैकिंग एल्गोरिदम रिसर्च फ्रेमवर्क, जिसमें कई बिन पैकिंग एल्गोरिदम और परीक्षण डेटा सम्मिलित हैं।

संदर्भ

↑ Martello, Silvano; Toth, Paolo (1990), "Bin-packing problem" (PDF), Knapsack Problems: Algorithms and Computer Implementations, Chichester, UK: John Wiley and Sons, ISBN 0471924202
↑ Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing". Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21. Springer. pp. 426–441. doi:10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
↑ Barrington, David Mix (2006). "बिन पैकिंग". Archived from the original on 2019-02-16. Retrieved 2016-02-27.
↑ ^4.0 ^4.1 ^4.2 Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Bin Packing Approximation Algorithms: Survey and Classification", Handbook of Combinatorial Optimization (in English), New York, NY: Springer, pp. 455–531, doi:10.1007/978-1-4419-7997-1_35, ISBN 978-1-4419-7997-1, retrieved 2021-08-08
↑ Lewis, R. (2009), "A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing" (PDF), Computers and Operations Research, 36 (7): 2295–2310, doi:10.1016/j.cor.2008.09.004
↑ Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), "Sharing-Aware Algorithms for Virtual Machine Colocation" (PDF), Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367–378
↑ ^7.0 ^7.1 ^7.2 Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.
↑ Martello & Toth 1990, p. 221
↑ Vazirani, Vijay V. (14 March 2013). सन्निकटन एल्गोरिदम. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657.
↑ ^10.00 ^10.01 ^10.02 ^10.03 ^10.04 ^10.05 ^10.06 ^10.07 ^10.08 ^10.09 ^10.10 ^10.11 ^10.12 ^10.13 ^10.14 ^10.15 Johnson, David S (1973). "लगभग-इष्टतम बिन पैकिंग एल्गोरिदम" (PDF). Massachusetts Institute of Technology.
↑ Gonzalez, Teofilo F. (23 May 2018). Handbook of approximation algorithms and metaheuristics. Volume 2 Contemporary and emerging applications. ISBN 9781498770156.
↑ ^12.0 ^12.1 ^12.2 Dósa, György; Sgall, Jiri (2013). "फर्स्ट फ़िट बिन पैकिंग: एक कड़ा विश्लेषण". 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. 20: 538–549. doi:10.4230/LIPIcs.STACS.2013.538.
↑ ^13.0 ^13.1 ^13.2 György, Dósa; Sgall, Jirí (2014). "सर्वश्रेष्ठ फ़िट बिन पैकिंग का इष्टतम विश्लेषण". {Automata, Languages, and Programming – 41st International Colloquium (ICALP)}. Lecture Notes in Computer Science. 8572: 429–441. doi:10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0.
↑ ^14.0 ^14.1 ^14.2 ^14.3 ^14.4 Yao, Andrew Chi-Chih (April 1980). "बिन पैकिंग के लिए नए एल्गोरिदम". Journal of the ACM. 27 (2): 207–227. doi:10.1145/322186.322187. S2CID 7903339.
↑ ^15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 ^15.6 Lee, C. C.; Lee, D. T. (July 1985). "एक सरल ऑनलाइन बिन-पैकिंग एल्गोरिदम". Journal of the ACM. 32 (3): 562–572. doi:10.1145/3828.3833. S2CID 15441740.
↑ Donna J, Brown (1979). "ऑन-लाइन एक-आयामी बिन पैकिंग एल्गोरिदम के लिए निचली सीमा।" (PDF). Technical Rept. Archived (PDF) from the original on March 17, 2022.
↑ Liang, Frank M. (1980). "ऑन-लाइन बिन पैकिंग के लिए निचली सीमा". Information Processing Letters. 10 (2): 76–79. doi:10.1016/S0020-0190(80)90077-0.
↑ van Vliet, André (1992). "ऑन-लाइन बिन पैकिंग एल्गोरिदम के लिए एक बेहतर निचली सीमा". Information Processing Letters. 43 (5): 277–284. doi:10.1016/0020-0190(92)90223-I.
↑ Balogh, János; Békési, József; Galambos, Gábor (July 2012). "बिन पैकिंग एल्गोरिदम के कुछ वर्गों के लिए नई निचली सीमाएँ". Theoretical Computer Science. 440–441: 1–13. doi:10.1016/j.tcs.2012.04.017.
↑ ^20.0 ^20.1 Ramanan, Prakash; Brown, Donna J; Lee, C.C; Lee, D.T (September 1989). "On-line bin packing in linear time". Journal of Algorithms. 10 (3): 305–326. doi:10.1016/0196-6774(89)90031-X. hdl:2142/74206.
↑ ^21.0 ^21.1 ^21.2 Seiden, Steven S. (2002). "On the online bin packing problem". Journal of the ACM. 49 (5): 640–671. doi:10.1145/585265.585269. S2CID 14164016.
↑ ^22.0 ^22.1 ^22.2 Dósa, György (2007). "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE. doi:10.1007/978-3-540-74450-4_1.
↑ Baker, B. S.; Coffman, Jr., E. G. (1981-06-01). "नेक्स्ट-फ़िट-घटते बिन-पैकिंग के लिए एक सख्त एसिम्प्टोटिक बाउंड". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 147–152. doi:10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Csirik, J.; Galambos, G.; Frenk, J.B.G.; Frieze, A.M.; Rinnooy Kan, A.H.G. (1986-11-01). "अगले फिट घटते बिन पैकिंग अनुमान का एक संभाव्य विश्लेषण". Operations Research Letters (in English). 5 (5): 233–236. doi:10.1016/0167-6377(86)90013-1. hdl:1765/11645. ISSN 0167-6377.
↑ Fisher, David C. (1988-12-01). "नेक्स्ट-फ़िट एक सूची को पैक करता है और उसे समान संख्या में डिब्बे में उलट देता है". Operations Research Letters (in English). 7 (6): 291–293. doi:10.1016/0167-6377(88)90060-0. ISSN 0167-6377.
↑ ^26.0 ^26.1 Johnson, David S; Garey, Michael R (October 1985). "A 7160 theorem for bin packing". Journal of Complexity. 1 (1): 65–106. doi:10.1016/0885-064X(85)90022-6.
↑ ^27.0 ^27.1 Yue, Minyi; Zhang, Lei (July 1995). "A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 11 (3): 318–330. doi:10.1007/BF02011198. S2CID 118263129.
↑ Fernandez de la Vega, W.; Lueker, G. S. (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica (in English). 1 (4): 349–355. doi:10.1007/BF02579456. ISSN 1439-6912. S2CID 10519631.
↑ Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera. Archived from the original on 2021-07-15.
↑ ^30.0 ^30.1 Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT · Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.
↑ ^31.0 ^31.1 Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10
↑ Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.
↑ Martello & Toth 1990, pp. 237–240.
↑ Korf, Richard E. (2002). इष्टतम बिन पैकिंग के लिए एक नया एल्गोरिदम। (PDF). AAAI-02.
↑ R. E. Korf (2003), An improved algorithm for optimal bin packing. Proceedings of the International Joint Conference on Artificial Intelligence, (pp. 1252–1258)
↑ Schreiber, Ethan L.; Korf, Richard E. (2013), "Improved Bin Completion for Optimal Bin Packing and Number Partitioning" (PDF), Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13, Beijing, China: AAAI Press, pp. 651–658, ISBN 978-1-57735-633-2
↑ ^37.0 ^37.1 Mandal, C. A.; Chakrabarti, P. P.; Ghose, S. (1998-06-01). "खंडित वस्तु बिन पैकिंग और एक अनुप्रयोग की जटिलता". Computers & Mathematics with Applications (in English). 35 (11): 91–97. doi:10.1016/S0898-1221(98)00087-X. ISSN 0898-1221.
↑ Nir Menakerman and Raphael Rom "Bin Packing with Item Fragmentation". Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings.
↑ Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (2019-05-31). "The Bin Packing Problem with Item Fragmentation:A worst-case analysis". Discrete Applied Mathematics. GO X Meeting, Rigi Kaltbad (CH), July 10--14, 2016 (in English). 261: 63–77. doi:10.1016/j.dam.2018.08.023. ISSN 0166-218X. S2CID 125361557.
↑ Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). Erlebach, Thomas; Persinao, Giuseppe (eds.). "आइटम विखंडन के साथ पैकिंग के लिए अनुमानित योजनाएं". Approximation and Online Algorithms. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 3879: 334–347. doi:10.1007/11671411_26. ISBN 978-3-540-32208-5.
↑ Ekici, Ali (2021-02-01). "संघर्ष और वस्तु विखंडन के साथ बिन पैकिंग की समस्या". Computers & Operations Research (in English). 126: 105113. doi:10.1016/j.cor.2020.105113. ISSN 0305-0548. S2CID 225002556.
↑ Casazza, Marco; Ceselli, Alberto (2014-06-01). "आइटम विखंडन के साथ बिन पैकिंग समस्याओं के लिए गणितीय प्रोग्रामिंग एल्गोरिदम". Computers & Operations Research (in English). 46: 1–11. doi:10.1016/j.cor.2013.12.008. ISSN 0305-0548.
↑ Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (2019-03-16). "Integer optimization with penalized fractional values: The Knapsack case". European Journal of Operational Research (in English). 273 (3): 874–888. doi:10.1016/j.ejor.2018.09.020. ISSN 0377-2217. S2CID 31722681.
↑ Krause, K. L.; Shen, V. Y.; Schwetman, H. D. (1975-10-01). "मल्टीप्रोग्रामिंग कंप्यूटर सिस्टम के एक मॉडल के लिए कई कार्य-शेड्यूलिंग एल्गोरिदम का विश्लेषण". Journal of the ACM. 22 (4): 522–550. doi:10.1145/321906.321917. ISSN 0004-5411. S2CID 10214857.
↑ Kellerer, H.; Pferschy, U. (1999-01-01). "Cardinality constrained bin‐packing problems". Annals of Operations Research (in English). 92: 335–348. doi:10.1023/A:1018947117526. ISSN 1572-9338. S2CID 28963291.
↑ ^46.0 ^46.1 Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "सामान्य लागत संरचनाओं के साथ बिन पैकिंग समस्या के लिए अनुमानों का सबसे खराब स्थिति वाला विश्लेषण". Operations Research. 42 (2): 287–298. doi:10.1287/opre.42.2.287. ISSN 0030-364X.
↑ Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (2019-07-01). "Overcommitment in Cloud Services: Bin Packing with Chance Constraints". Management Science. 65 (7): 3255–3271. arXiv:1705.09335. doi:10.1287/mnsc.2018.3091. ISSN 0025-1909. S2CID 159270392.
↑ Chung, Yerim; Park, Myoung-Ju (2015-01-01). "व्युत्क्रम बिन-पैकिंग समस्याओं पर नोट्स". Information Processing Letters (in English). 115 (1): 60–68. doi:10.1016/j.ipl.2014.09.005. ISSN 0020-0190.
↑ Boyar, Joan; Epstein, Leah; Favrholdt, Lene M.; Kohrt, Jens S.; Larsen, Kim S.; Pedersen, Morten M.; Wøhlk, Sanne (2006-10-11). "अधिकतम संसाधन बिन पैकिंग समस्या". Theoretical Computer Science (in English). 362 (1): 127–139. doi:10.1016/j.tcs.2006.06.001. ISSN 0304-3975.
↑ Huang, Xin; Lu, Pinyan (2020-11-10). "कामकाज के अधिकतम शेयर आवंटन का अनुमान लगाने के लिए एक एल्गोरिदमिक ढांचा". arXiv:1907.04505 [cs.GT].
↑ Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). "स्वार्थी बिन पैकिंग समस्या पर एक नोट". Journal of Global Optimization. 56 (4): 1457–1462. doi:10.1007/s10898-012-9856-9. ISSN 0925-5001. S2CID 3082040.
↑ Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Two-Dimensional Bin Packing Problems". In V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization, Wiley/ISTE, pp. 107–129
↑ Optimizing Three-Dimensional Bin Packing Through Simulation
↑ Benkő A., Dósa G., Tuza Z. (2010) "Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms," Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, pp. 298–302.
↑ Vaccaro, Alessio (2020-11-13). "🧱 4 Steps to Easily Allocate Resources with Python & Bin Packing". Medium (in English). Retrieved 2021-03-21.

[1] Martello, Silvano; Toth, Paolo (1990), "Bin-packing problem" (PDF), Knapsack Problems: Algorithms and Computer Implementations, Chichester, UK: John Wiley and Sons, ISBN 0471924202

[2] Korte, Bernhard; Vygen, Jens (2006). "Bin-Packing". Combinatorial Optimization: Theory and Algorithms. Algorithms and Combinatorics 21. Springer. pp. 426–441. doi:10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.

[3] Barrington, David Mix (2006). "बिन पैकिंग". Archived from the original on 2019-02-16. Retrieved 2016-02-27.

[:0-4] 4.0 ^4.1 ^4.2 Coffman Jr., Edward G.; Csirik, János; Galambos, Gábor; Martello, Silvano; Vigo, Daniele (2013), Pardalos, Panos M.; Du, Ding-Zhu; Graham, Ronald L. (eds.), "Bin Packing Approximation Algorithms: Survey and Classification", Handbook of Combinatorial Optimization (in English), New York, NY: Springer, pp. 455–531, doi:10.1007/978-1-4419-7997-1_35, ISBN 978-1-4419-7997-1, retrieved 2021-08-08

[5] Lewis, R. (2009), "A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing" (PDF), Computers and Operations Research, 36 (7): 2295–2310, doi:10.1016/j.cor.2008.09.004

[6] Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), "Sharing-Aware Algorithms for Virtual Machine Colocation" (PDF), Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367–378

[GareyJohnson2-7] 7.0 ^7.1 ^7.2 Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 0-7167-1045-5. MR 0519066.

[Martello19902-8] Martello & Toth 1990, p. 221

[9] Vazirani, Vijay V. (14 March 2013). सन्निकटन एल्गोरिदम. Springer Berlin Heidelberg. p. 74. ISBN 978-3662045657.

[johnson732-10] 10.00 ^10.01 ^10.02 ^10.03 ^10.04 ^10.05 ^10.06 ^10.07 ^10.08 ^10.09 ^10.10 ^10.11 ^10.12 ^10.13 ^10.14 ^10.15 Johnson, David S (1973). "लगभग-इष्टतम बिन पैकिंग एल्गोरिदम" (PDF). Massachusetts Institute of Technology.

[11] Gonzalez, Teofilo F. (23 May 2018). Handbook of approximation algorithms and metaheuristics. Volume 2 Contemporary and emerging applications. ISBN 9781498770156.

[DósaSgall2-12] 12.0 ^12.1 ^12.2 Dósa, György; Sgall, Jiri (2013). "फर्स्ट फ़िट बिन पैकिंग: एक कड़ा विश्लेषण". 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. 20: 538–549. doi:10.4230/LIPIcs.STACS.2013.538.

[DósaSgall142-13] 13.0 ^13.1 ^13.2 György, Dósa; Sgall, Jirí (2014). "सर्वश्रेष्ठ फ़िट बिन पैकिंग का इष्टतम विश्लेषण". {Automata, Languages, and Programming – 41st International Colloquium (ICALP)}. Lecture Notes in Computer Science. 8572: 429–441. doi:10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0.

[Yao19802-14] 14.0 ^14.1 ^14.2 ^14.3 ^14.4 Yao, Andrew Chi-Chih (April 1980). "बिन पैकिंग के लिए नए एल्गोरिदम". Journal of the ACM. 27 (2): 207–227. doi:10.1145/322186.322187. S2CID 7903339.

[LeeLee19852-15] 15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 ^15.6 Lee, C. C.; Lee, D. T. (July 1985). "एक सरल ऑनलाइन बिन-पैकिंग एल्गोरिदम". Journal of the ACM. 32 (3): 562–572. doi:10.1145/3828.3833. S2CID 15441740.

[16] Donna J, Brown (1979). "ऑन-लाइन एक-आयामी बिन पैकिंग एल्गोरिदम के लिए निचली सीमा।" (PDF). Technical Rept. Archived (PDF) from the original on March 17, 2022.

[17] Liang, Frank M. (1980). "ऑन-लाइन बिन पैकिंग के लिए निचली सीमा". Information Processing Letters. 10 (2): 76–79. doi:10.1016/S0020-0190(80)90077-0.

[18] van Vliet, André (1992). "ऑन-लाइन बिन पैकिंग एल्गोरिदम के लिए एक बेहतर निचली सीमा". Information Processing Letters. 43 (5): 277–284. doi:10.1016/0020-0190(92)90223-I.

[19] Balogh, János; Békési, József; Galambos, Gábor (July 2012). "बिन पैकिंग एल्गोरिदम के कुछ वर्गों के लिए नई निचली सीमाएँ". Theoretical Computer Science. 440–441: 1–13. doi:10.1016/j.tcs.2012.04.017.

[RamananBLL19892-20] 20.0 ^20.1 Ramanan, Prakash; Brown, Donna J; Lee, C.C; Lee, D.T (September 1989). "On-line bin packing in linear time". Journal of Algorithms. 10 (3): 305–326. doi:10.1016/0196-6774(89)90031-X. hdl:2142/74206.

[Seiden20022-21] 21.0 ^21.1 ^21.2 Seiden, Steven S. (2002). "On the online bin packing problem". Journal of the ACM. 49 (5): 640–671. doi:10.1145/585265.585269. S2CID 14164016.

[Dosa072-22] 22.0 ^22.1 ^22.2 Dósa, György (2007). "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. ESCAPE. doi:10.1007/978-3-540-74450-4_1.

[23] Baker, B. S.; Coffman, Jr., E. G. (1981-06-01). "नेक्स्ट-फ़िट-घटते बिन-पैकिंग के लिए एक सख्त एसिम्प्टोटिक बाउंड". SIAM Journal on Algebraic and Discrete Methods. 2 (2): 147–152. doi:10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[24] Csirik, J.; Galambos, G.; Frenk, J.B.G.; Frieze, A.M.; Rinnooy Kan, A.H.G. (1986-11-01). "अगले फिट घटते बिन पैकिंग अनुमान का एक संभाव्य विश्लेषण". Operations Research Letters (in English). 5 (5): 233–236. doi:10.1016/0167-6377(86)90013-1. hdl:1765/11645. ISSN 0167-6377.

[25] Fisher, David C. (1988-12-01). "नेक्स्ट-फ़िट एक सूची को पैक करता है और उसे समान संख्या में डिब्बे में उलट देता है". Operations Research Letters (in English). 7 (6): 291–293. doi:10.1016/0167-6377(88)90060-0. ISSN 0167-6377.

[JohnsonGarey19852-26] 26.0 ^26.1 Johnson, David S; Garey, Michael R (October 1985). "A 7160 theorem for bin packing". Journal of Complexity. 1 (1): 65–106. doi:10.1016/0885-064X(85)90022-6.

[YueZhang19952-27] 27.0 ^27.1 Yue, Minyi; Zhang, Lei (July 1995). "A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm". Acta Mathematicae Applicatae Sinica. 11 (3): 318–330. doi:10.1007/BF02011198. S2CID 118263129.

[28] Fernandez de la Vega, W.; Lueker, G. S. (1981). "Bin packing can be solved within 1 + ε in linear time". Combinatorica (in English). 1 (4): 349–355. doi:10.1007/BF02579456. ISSN 1439-6912. S2CID 10519631.

[29] Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera. Archived from the original on 2021-07-15.

[:2-30] 30.0 ^30.1 Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT · Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.

[:3-31] 31.0 ^31.1 Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10

[:1-32] Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.

[33] Martello & Toth 1990, pp. 237–240.

[34] Korf, Richard E. (2002). इष्टतम बिन पैकिंग के लिए एक नया एल्गोरिदम। (PDF). AAAI-02.

[Korf2003Korf2-35] R. E. Korf (2003), An improved algorithm for optimal bin packing. Proceedings of the International Joint Conference on Artificial Intelligence, (pp. 1252–1258)

[36] Schreiber, Ethan L.; Korf, Richard E. (2013), "Improved Bin Completion for Optimal Bin Packing and Number Partitioning" (PDF), Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13, Beijing, China: AAAI Press, pp. 651–658, ISBN 978-1-57735-633-2

[:03-37] 37.0 ^37.1 Mandal, C. A.; Chakrabarti, P. P.; Ghose, S. (1998-06-01). "खंडित वस्तु बिन पैकिंग और एक अनुप्रयोग की जटिलता". Computers & Mathematics with Applications (in English). 35 (11): 91–97. doi:10.1016/S0898-1221(98)00087-X. ISSN 0898-1221.

[38] Nir Menakerman and Raphael Rom "Bin Packing with Item Fragmentation". Algorithms and Data Structures, 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001, Proceedings.

[39] Bertazzi, Luca; Golden, Bruce; Wang, Xingyin (2019-05-31). "The Bin Packing Problem with Item Fragmentation:A worst-case analysis". Discrete Applied Mathematics. GO X Meeting, Rigi Kaltbad (CH), July 10--14, 2016 (in English). 261: 63–77. doi:10.1016/j.dam.2018.08.023. ISSN 0166-218X. S2CID 125361557.

[40] Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). Erlebach, Thomas; Persinao, Giuseppe (eds.). "आइटम विखंडन के साथ पैकिंग के लिए अनुमानित योजनाएं". Approximation and Online Algorithms. Lecture Notes in Computer Science (in English). Berlin, Heidelberg: Springer. 3879: 334–347. doi:10.1007/11671411_26. ISBN 978-3-540-32208-5.

[41] Ekici, Ali (2021-02-01). "संघर्ष और वस्तु विखंडन के साथ बिन पैकिंग की समस्या". Computers & Operations Research (in English). 126: 105113. doi:10.1016/j.cor.2020.105113. ISSN 0305-0548. S2CID 225002556.

[42] Casazza, Marco; Ceselli, Alberto (2014-06-01). "आइटम विखंडन के साथ बिन पैकिंग समस्याओं के लिए गणितीय प्रोग्रामिंग एल्गोरिदम". Computers & Operations Research (in English). 46: 1–11. doi:10.1016/j.cor.2013.12.008. ISSN 0305-0548.

[43] Malaguti, Enrico; Monaci, Michele; Paronuzzi, Paolo; Pferschy, Ulrich (2019-03-16). "Integer optimization with penalized fractional values: The Knapsack case". European Journal of Operational Research (in English). 273 (3): 874–888. doi:10.1016/j.ejor.2018.09.020. ISSN 0377-2217. S2CID 31722681.

[44] Krause, K. L.; Shen, V. Y.; Schwetman, H. D. (1975-10-01). "मल्टीप्रोग्रामिंग कंप्यूटर सिस्टम के एक मॉडल के लिए कई कार्य-शेड्यूलिंग एल्गोरिदम का विश्लेषण". Journal of the ACM. 22 (4): 522–550. doi:10.1145/321906.321917. ISSN 0004-5411. S2CID 10214857.

[45] Kellerer, H.; Pferschy, U. (1999-01-01). "Cardinality constrained bin‐packing problems". Annals of Operations Research (in English). 92: 335–348. doi:10.1023/A:1018947117526. ISSN 1572-9338. S2CID 28963291.

[pubsonline.informs.org-46] 46.0 ^46.1 Anily, Shoshana; Bramel, Julien; Simchi-Levi, David (1994-04-01). "सामान्य लागत संरचनाओं के साथ बिन पैकिंग समस्या के लिए अनुमानों का सबसे खराब स्थिति वाला विश्लेषण". Operations Research. 42 (2): 287–298. doi:10.1287/opre.42.2.287. ISSN 0030-364X.

[47] Cohen, Maxime C.; Keller, Philipp W.; Mirrokni, Vahab; Zadimoghaddam, Morteza (2019-07-01). "Overcommitment in Cloud Services: Bin Packing with Chance Constraints". Management Science. 65 (7): 3255–3271. arXiv:1705.09335. doi:10.1287/mnsc.2018.3091. ISSN 0025-1909. S2CID 159270392.

[48] Chung, Yerim; Park, Myoung-Ju (2015-01-01). "व्युत्क्रम बिन-पैकिंग समस्याओं पर नोट्स". Information Processing Letters (in English). 115 (1): 60–68. doi:10.1016/j.ipl.2014.09.005. ISSN 0020-0190.

[:02-49] Boyar, Joan; Epstein, Leah; Favrholdt, Lene M.; Kohrt, Jens S.; Larsen, Kim S.; Pedersen, Morten M.; Wøhlk, Sanne (2006-10-11). "अधिकतम संसाधन बिन पैकिंग समस्या". Theoretical Computer Science (in English). 362 (1): 127–139. doi:10.1016/j.tcs.2006.06.001. ISSN 0304-3975.

[50] Huang, Xin; Lu, Pinyan (2020-11-10). "कामकाज के अधिकतम शेयर आवंटन का अनुमान लगाने के लिए एक एल्गोरिदमिक ढांचा". arXiv:1907.04505 [cs.GT].

[51] Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). "स्वार्थी बिन पैकिंग समस्या पर एक नोट". Journal of Global Optimization. 56 (4): 1457–1462. doi:10.1007/s10898-012-9856-9. ISSN 0925-5001. S2CID 3082040.

[52] Lodi A., Martello S., Monaci, M., Vigo, D. (2010) "Two-Dimensional Bin Packing Problems". In V.Th. Paschos (Ed.), Paradigms of Combinatorial Optimization, Wiley/ISTE, pp. 107–129

[53] Optimizing Three-Dimensional Bin Packing Through Simulation

[54] Benkő A., Dósa G., Tuza Z. (2010) "Bin Packing/Covering with Delivery, Solved with the Evolution of Algorithms," Proceedings 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, art. no. 5645312, pp. 298–302.

[55] Vaccaro, Alessio (2020-11-13). "🧱 4 Steps to Easily Allocate Resources with Python & Bin Packing". Medium (in English). Retrieved 2021-03-21.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

@@ Line 1: / Line 1: @@
-{{Short description|Mathematical and computational problem}}
+{{Short description|Mathematical and computational problem}}{{Covering/packing-problem pairs}}
-{{Distinguish|बिन पैकिंग}}
-{{Covering/packing-problem pairs}}
+'''बिन पैकिंग समस्या'''<ref>{{citation|last1=Martello|first1=Silvano|title=Knapsack Problems: Algorithms and Computer Implementations|url=https://archive.org/details/knapsackproblems0000mart|year=1990|chapter=Bin-packing problem|chapter-url=http://www.or.deis.unibo.it/kp/Chapter8.pdf|location=Chichester, UK|publisher=John Wiley and Sons|isbn=0471924202|last2=Toth|first2=Paolo|url-access=registration}}</ref><ref>{{cite book|last1=Korte|first1=Bernhard|title=Combinatorial Optimization: Theory and Algorithms|last2=Vygen|first2=Jens|publisher=Springer|year=2006|isbn=978-3-540-25684-7|series=Algorithms and Combinatorics 21|pages=426–441|chapter=Bin-Packing|doi=10.1007/3-540-29297-7_18|chapter-url=https://books.google.com/books?id=UnYwgPltSjwC&q=Bin-Packing&pg=PA449}}</ref><ref>{{cite web|last=Barrington|first=David Mix|year=2006|title=बिन पैकिंग|url=https://people.cs.umass.edu/~barring/cs311/disc/11.html|url-status=dead|archive-url=https://web.archive.org/web/20190216134619/https://people.cs.umass.edu/~barring/cs311/disc/11.html|archive-date=2019-02-16|access-date=2016-02-27}}</ref><ref name=":0">{{Citation|last1=Coffman Jr.|first1=Edward G.|title=Bin Packing Approximation Algorithms: Survey and Classification|date=2013|url=https://doi.org/10.1007/978-1-4419-7997-1_35|work=Handbook of Combinatorial Optimization|pages=455–531|editor-last=Pardalos|editor-first=Panos M.|place=New York, NY|publisher=Springer|language=en|doi=10.1007/978-1-4419-7997-1_35|isbn=978-1-4419-7997-1|access-date=2021-08-08|last2=Csirik|first2=János|last3=Galambos|first3=Gábor|last4=Martello|first4=Silvano|last5=Vigo|first5=Daniele|editor2-last=Du|editor2-first=Ding-Zhu|editor3-last=Graham|editor3-first=Ronald L.}}</ref> एक [[अनुकूलन समस्या]] है, जिसमें विभिन्न आकार की वस्तुओं को सीमित संख्या में बिन में पैक किया जाना चाहिए या प्रत्येक निश्चित क्षमता के कंटेनर, इस तरह से कि उपयोग किए गए बिन की संख्या कम से कम हो। समस्या जैसे कंटेनर भरना, वजन क्षमता की कमी वाले ट्रकों को लोड करना, मीडिया में फ़ाइल [[बैकअप]] बनाना और एफपीजीए [[ अर्धचालक चिप |अर्धचालक चिप]] डिजाइन में प्रौद्योगिकी मैपिंग के कई अनुप्रयोग हैं।
-बिन पैकिंग समस्या<ref>{{citation|last1=Martello|first1=Silvano|title=Knapsack Problems: Algorithms and Computer Implementations|url=https://archive.org/details/knapsackproblems0000mart|year=1990|chapter=Bin-packing problem|chapter-url=http://www.or.deis.unibo.it/kp/Chapter8.pdf|location=Chichester, UK|publisher=John Wiley and Sons|isbn=0471924202|last2=Toth|first2=Paolo|url-access=registration}}</ref><ref>{{cite book|last1=Korte|first1=Bernhard|title=Combinatorial Optimization: Theory and Algorithms|last2=Vygen|first2=Jens|publisher=Springer|year=2006|isbn=978-3-540-25684-7|series=Algorithms and Combinatorics 21|pages=426–441|chapter=Bin-Packing|doi=10.1007/3-540-29297-7_18|chapter-url=https://books.google.com/books?id=UnYwgPltSjwC&q=Bin-Packing&pg=PA449}}</ref><ref>{{cite web|last=Barrington|first=David Mix|year=2006|title=बिन पैकिंग|url=https://people.cs.umass.edu/~barring/cs311/disc/11.html|url-status=dead|archive-url=https://web.archive.org/web/20190216134619/https://people.cs.umass.edu/~barring/cs311/disc/11.html|archive-date=2019-02-16|access-date=2016-02-27}}</ref><ref name=":0">{{Citation|last1=Coffman Jr.|first1=Edward G.|title=Bin Packing Approximation Algorithms: Survey and Classification|date=2013|url=https://doi.org/10.1007/978-1-4419-7997-1_35|work=Handbook of Combinatorial Optimization|pages=455–531|editor-last=Pardalos|editor-first=Panos M.|place=New York, NY|publisher=Springer|language=en|doi=10.1007/978-1-4419-7997-1_35|isbn=978-1-4419-7997-1|access-date=2021-08-08|last2=Csirik|first2=János|last3=Galambos|first3=Gábor|last4=Martello|first4=Silvano|last5=Vigo|first5=Daniele|editor2-last=Du|editor2-first=Ding-Zhu|editor3-last=Graham|editor3-first=Ronald L.}}</ref> एक [[अनुकूलन समस्या]] है, जिसमें विभिन्न आकार की वस्तुओं को सीमित संख्या में बिन में पैक किया जाना चाहिए या प्रत्येक निश्चित क्षमता के कंटेनर, इस तरह से कि उपयोग किए गए बिन की संख्या कम से कम हो। समस्या जैसे कंटेनर भरना, वजन क्षमता की कमी वाले ट्रकों को लोड करना, मीडिया में फ़ाइल [[बैकअप]] बनाना और एफपीजीए [[ अर्धचालक चिप |अर्धचालक चिप]] डिजाइन में प्रौद्योगिकी मैपिंग के कई अनुप्रयोग हैं।
 कम्प्यूटेशनल रूप से, समस्या एनपी-हार्ड है, और संबंधित निर्णय समस्या - यह तय करना कि क्या वस्तुएं निर्दिष्ट संख्या में बिन में फिट हो सकती हैं -एनपी-कम्पलीट है। इसकी सबसे निकृष्ट स्थिति के बावजूद, समस्या के बहुत बड़े उदाहरणों के लिए इष्टतम समाधान रिफाइंड एल्गोरिदम के साथ उत्पादित किए जा सकते हैं। इसके अतिरिक्त, अनेक सन्निकटन एल्गोरिदम उपस्थित हैं। उदाहरण के लिए, पहला फ़िट एल्गोरिथ्म तेज़ लेकिन प्रायः गैर-इष्टतम समाधान प्रदान करता है, जिसमें प्रत्येक वस्तु को पहले बिन में रखना सम्मिलित होता है जिसमें वह फिट होगा। इसके लिए ''Θ''(''n'' log ''n'') समय की आवश्यकता होती है, जहां ''n'' पैक किए जाने वाले वस्तु की संख्या है। वस्तुओं की सूची को पहले घटते क्रम में क्रमबद्ध करके एल्गोरिदम को और अधिक प्रभावी बनाया जा सकता है (कभी-कभी इसे प्रथम-फिट घटते एल्गोरिदम के रूप में जाना जाता है), हालाँकि यह अभी भी एक इष्टतम समाधान की गारंटी नहीं देता है और लंबी सूचियों के लिए एल्गोरिदम के चलने के समय में वृद्धि हो सकती है। हालाँकि, यह ज्ञात है कि वस्तुओं का कम से कम ऑर्डर हमेशा उपस्थित रहता है जो फर्स्ट-फ़िट को इष्टतम समाधान तैयार करने की अनुमति देता है।<ref>{{citation|last=Lewis|first=R.|title=A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing|url=http://orca.cf.ac.uk/11334/1/Lewis%2C_R_General_Purpose_Hill_Climbing.pdf|journal=Computers and Operations Research|volume=36|issue=7|pages=2295–2310|year=2009|doi=10.1016/j.cor.2008.09.004}}</ref>
@@ Line 17: / Line 14: @@
 कंप्यूटर और इंट्रैक्टेबिलिटी में<ref name="GareyJohnson2">{{cite book|last1=Garey|first1=M.&nbsp;R.|title=<!-- [[ -->Computers and Intractability: A Guide to the Theory of NP-Completeness<!-- ]] -->|last2=Johnson|first2=D.&nbsp;S.|publisher=W.&nbsp;H.&nbsp;Freeman and Co.|year=1979|isbn=0-7167-1045-5|editor=Victor Klee|editor-link=Victor Klee|series=A Series of Books in the Mathematical Sciences|location=San Francisco, Calif.|pages=[https://archive.org/details/computersintract0000gare/page/ x+338]|mr=519066|author-link1=Michael R. Garey|author-link2=David S. Johnson}}</ref>{{Rp|226}} गैरी और जॉनसन ने संदर्भ [SR1] के तहत बिन पैकिंग समस्या को सूचीबद्ध किया है। वे इसके निर्णय प्रकार को निम्नानुसार परिभाषित करते हैं।
-उदाहरण: परिमित समुच्चय <math>I</math> वस्तुओं का, आकार <math>s(i) \in \mathbb{Z}^+</math> प्रत्येक के लिए <math>i \in I</math>, धनात्मक पूर्णांक बिन क्षमता <math>B</math>, और  सकारात्मक पूर्णांक <math>K</math>.
+उदाहरण: परिमित समुच्चय <math>I</math> वस्तुओं का, आकार <math>s(i) \in \mathbb{Z}^+</math> प्रत्येक के लिए <math>i \in I</math>, धनात्मक पूर्णांक बिन क्षमता <math>B</math>, और  धनात्मक पूर्णांक <math>K</math>.
 प्रश्न: क्या इसका कोई विभाजन है? <math>I</math> [[असंयुक्त सेट|असंयुक्त समुच्चय]] में <math>I_1,\dots, I_K</math> इस प्रकार कि प्रत्येक में वस्तु के आकार का योग <math>I_j</math> <math>B</math> या कम है?
@@ Line 48: / Line 45: @@
 |}
 जहाँ <math> y_j = 1</math> अगर वहां था <math>j</math> प्रयोग किया जाता है और <math> x_{ij} = 1</math> यदि वस्तु <math>i</math> बिन <math>j</math> में डाल दिया जाता है<ref name="Martello19902">{{harvnb|Martello|Toth|1990|p=221}}</ref>
 == बिन पैकिंग की कठोरता ==
-बिन पैकिंग समस्या सशक्त एनपी-पूर्णता|दृढ़तापूर्वक एनपी-पूर्णता है। इसे बिन पैकिंग में एनपी-कम्पलीट 3-विभाजन समस्या को कम करके सिद्ध किया जा सकता है।<ref name="GareyJohnson2" />
+बिन पैकिंग समस्या सशक्त NP-पूर्णता दृढ़तापूर्वक एनपी-पूर्णता है। इसे बिन पैकिंग में एनपी-कम्पलीट 3-विभाजन समस्या को कम करके सिद्ध किया जा सकता है।<ref name="GareyJohnson2" />
 इसके अलावा, पूर्ण सन्निकटन अनुपात से छोटा कोई सन्निकटन एल्गोरिदम नहीं हो सकता है <math>\tfrac 3 2</math> जब तक <math>\mathsf{P} = \mathsf{NP}</math>. इसे विभाजन समस्या को कम करके सिद्ध किया जा सकता है:<ref>{{cite book|last1=Vazirani|first1=Vijay V.|title=सन्निकटन एल्गोरिदम|date=14 March 2013|publisher=Springer Berlin Heidelberg|isbn=978-3662045657|pages=74}}</ref> विभाजन का एक उदाहरण दिया गया है जहां सभी इनपुट संख्याओं का योग <math>2T</math> है, बिन-पैकिंग का एक उदाहरण बनाएं जिसमें बिन का आकार हो {{mvar|T}}. यदि इनपुट का समान विभाजन उपस्थित है, तो इष्टतम पैकिंग के लिए 2 बिन की आवश्यकता होती है; इसलिए, प्रत्येक एल्गोरिदम का सन्निकटन अनुपात इससे छोटा होता है {{sfrac|3|2}} को 3 बिन से कम लौटाना होगा, जो कि 2 बिन होने चाहिए। इसके विपरीत, यदि इनपुट का कोई समान विभाजन नहीं है, तो इष्टतम पैकिंग के लिए कम से कम 3 बिन की आवश्यकता होती है।
@@ Line 302: / Line 298: @@
 {{Packing problem}}
-{{DEFAULTSORT:Bin Packing Problem}}[[Category: अनुकूलन एल्गोरिदम और विधियाँ]] [[Category: जोरदार एनपी-पूर्ण समस्याएं]] [[Category: बिन पैकिंग|*]]
+{{DEFAULTSORT:Bin Packing Problem}}
-[[Category: Machine Translated Page]]
+[[Category:CS1|Bin Packing Problem]]
-[[Category:Created On 26/07/2023]]
+[[Category:CS1 English-language sources (en)|Bin Packing Problem]]
+[[Category:Collapse templates|Bin Packing Problem]]
+[[Category:Created On 26/07/2023|Bin Packing Problem]]
+[[Category:Lua-based templates|Bin Packing Problem]]
+[[Category:Machine Translated Page|Bin Packing Problem]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Bin Packing Problem]]
+[[Category:Pages with script errors|Bin Packing Problem]]
+[[Category:Short description with empty Wikidata description|Bin Packing Problem]]
+[[Category:Sidebars with styles needing conversion|Bin Packing Problem]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Bin Packing Problem]]
+[[Category:Templates generating microformats|Bin Packing Problem]]
+[[Category:Templates that add a tracking category|Bin Packing Problem]]
+[[Category:Templates that are not mobile friendly|Bin Packing Problem]]
+[[Category:Templates that generate short descriptions|Bin Packing Problem]]
+[[Category:Templates using TemplateData|Bin Packing Problem]]
+[[Category:Wikipedia metatemplates|Bin Packing Problem]]
+[[Category:अनुकूलन एल्गोरिदम और विधियाँ|Bin Packing Problem]]
+[[Category:जोरदार एनपी-पूर्ण समस्याएं|Bin Packing Problem]]
+[[Category:बिन पैकिंग|*]]

v t e Packing problems
Abstract packing	Bin Set
Circle packing	In a circle / equilateral triangle / isosceles right triangle / square Apollonian gasket Circle packing theorem Tammes problem (on sphere)
Sphere packing	Apollonian Finite In a sphere In a cube In a cylinder Close-packing Kissing number Sphere-packing (Hamming) bound
Other 2-D packing	Square packing in a square
Other 3-D packing	Tetrahedron Ellipsoid
Puzzles	Conway Slothouber–Graatsma

Anonymous

Search

बिन पैकिंग की समस्या: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:12, 30 August 2023

Contents

औपचारिक कथन

बिन पैकिंग की कठोरता

बिन पैकिंग के लिए अनुमान एल्गोरिदम

ऑनलाइन अनुमान

सिंगल-क्लास एल्गोरिदम

रिफाइंड एल्गोरिदम

ऑनलाइन एल्गोरिदम के लिए सामान्य निचली सीमाएं

तुलना तालिका

ऑफ़लाइन एल्गोरिदम

गुणात्मक सन्निकटन

योगात्मक सन्निकटन

तुलना तालिका

सटीक एल्गोरिदम

विभिन्न आकारों की छोटी संख्या

विखंडन के साथ बिन-पैकिंग

वेरिएंट

कम्प्यूटेशनल जटिलता

संबंधित समस्याएँ

बिन पर कार्डिनैलिटी बाधाएँ

गैर-योगात्मक कार्य

संबंधित समस्याएँ

संसाधन

कार्यान्वयन

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बिन पैकिंग की समस्या: Difference between revisions

Latest revision as of 15:12, 30 August 2023

औपचारिक कथन

बिन पैकिंग की कठोरता

बिन पैकिंग के लिए अनुमान एल्गोरिदम

ऑनलाइन अनुमान

सिंगल-क्लास एल्गोरिदम

रिफाइंड एल्गोरिदम

ऑनलाइन एल्गोरिदम के लिए सामान्य निचली सीमाएं

तुलना तालिका

ऑफ़लाइन एल्गोरिदम

गुणात्मक सन्निकटन

योगात्मक सन्निकटन

तुलना तालिका

सटीक एल्गोरिदम

विभिन्न आकारों की छोटी संख्या

विखंडन के साथ बिन-पैकिंग

वेरिएंट

कम्प्यूटेशनल जटिलता

संबंधित समस्याएँ

बिन पर कार्डिनैलिटी बाधाएँ

गैर-योगात्मक कार्य

संबंधित समस्याएँ

संसाधन

कार्यान्वयन

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories