💻 computer science

A 2.37332-Competitive Algorithm for Online Square Packing with Gravity

यह शोध पत्र $\mathrm{AsymmetricSlots}$ एल्गोरिदम प्रस्तुत करता है, जो टेट्रिस और ग्रेविटी बाधाओं के तहत यूनिट-विड्थ स्ट्रिप में ऑनलाइन स्क्वायर पैकिंग के लिए 2.37332-प्रतिस्पर्धी अनुपात प्राप्त करता है, जो पिछले सर्वश्रेष्ठ लगभग 2.6154 के बाउंड को सुधारता है और साथ ही सामान्य आयतों के लिए आस्पेक्ट रेशियो पर इष्टतम निर्भरता स्थापित करता है।

मूल लेखक: Nichlas Langhoff Rasmussen

प्रकाशित 2026-09-10

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Nichlas Langhoff Rasmussen

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक ऐसी दुनिया में हैं जहाँ आपको एक मीनार बनानी है, एक बार में एक ब्लॉक के साथ, बिना यह देखे कि आगे क्या आने वाला है। आप पहले से रखे गए ब्लॉकों को पुनर्व्यवस्थित नहीं कर सकते, और न ही आप उन्हें हटाने के लिए संरचना के भीतर हाथ डाल सकते हैं। प्रत्येक नया ब्लॉक ऊपर से गिरना चाहिए, सीधे नीचे गिरते हुए जब तक कि वह मौजूदा ढेर के शीर्ष या फर्श से न टकरा जाए। यदि मीनार में कोई अंतराल (गैप) मौजूद है, लेकिन वह ऊपर से एक चौड़े ब्लॉक द्वारा अवरुद्ध है, तो वह अंतराल बेकार है; उस तक कुछ भी कभी नहीं पहुँच पाएगा। यह गुरुत्वाकर्षण के तहत ऑनलाइन पैकिंग की चुनौती है, जो ज्यामिति और रसद (लॉजिस्टिक्स) के मिलन बिंदु पर स्थित एक समस्या है। यह एक सरल लेकिन जिद्दी सवाल पूछती है: एक प्रणाली सर्वोत्तम संभव निर्णय कैसे ले सकती है जब वह भविष्य के प्रति अंधी हो और भौतिकी के नियमों से बंधी हो?

वर्षों से, इस तरह से वर्गाकार ब्लॉकों को रखने के लिए सबसे अच्छी ज्ञात विधि यह गारंटी दे सकती थी कि मीनार, यदि किसी ने सभी ब्लॉकों को पहले से देख लिया होता, तो बनने वाली सबसे छोटी मीनार से लगभग 2.62 गुना अधिक ऊँची होगी। ऑनलाइन वास्तविकता और ऑफलाइन आदर्श के बीच का यह अंतर एक महत्वपूर्ण अक्षमता को दर्शाता था। शोधकर्ताओं को लंबे समय से संदेह था कि स्थान को व्यवस्थित करने का एक स्मार्ट तरीका इस अंतर को पाट सकता है, लेकिन गुरुत्वाकर्षण की बाधाओं और भविष्य के ज्ञान के अभाव ने ऐसे तरीके को खोजना असाधारण रूप से कठिन बना दिया। यह केवल आकृतियों को एक साथ फिट करने के बारे में नहीं है; यह स्थान के प्रवाह को प्रबंधित करने के बारे में है जैसे-जैसे उसका उपभोग किया जाता है, यह सुनिश्चित करना कि भविष्य के ब्लॉकों के लिए मार्ग खुला रहे भले ही वर्तमान संरचना बढ़ती जाए।

एक हालिया अध्ययन एक नई रणनीति पेश करता है जिसे 'AsymmetricSlots' कहा जाता है, जो इस दक्षता अंतराल को सफलतापूर्वक कम करती है। शोधकर्ताओं ने एक ऐसी विधि विकसित की है जो पैकिंग एल्गोरिदम के सबसे खराब स्थिति वाले प्रदर्शन (worst-case performance) में सुधार करती है, यह सिद्ध करते हुए कि परिणामी मीनार कभी भी पूर्ण, पूर्व-नियोजित मीनार से लगभग 2.37 गुना अधिक ऊँची नहीं होगी। यह पिछले सर्वोत्तम परिणाम की तुलना में एक मापने योग्य सुधार है, जो ऑनलाइन वर्गाकार पैकिंग के सैद्धांतिक सीमा को आदर्श के काफी करीब लाता है। यह कार्य इस दावे के साथ नहीं आता कि इसने समस्या को पूरी तरह से हल कर दिया है, क्योंकि 2 के ज्ञात निचली सीमा और इस नए ऊपरी स्तर के बीच एक अंतर बना हुआ है, लेकिन यह जो कुछ भी प्राप्त किया जा सकता है, उसके लिए एक नया, उच्च मानक स्थापित करता है।

इस नए दृष्टिकोण का मूल आधार यह है कि उपलब्ध स्थान को कैसे विभाजित किया जाता है। पिछली विधियों ने ऊर्ध्वाधर पट्टी (vertical strip) के स्थान को समान आकार के, नेस्टेड कंपार्टमेंट्स की एक श्रृंखला के रूप में माना, जो हर स्तर पर चौड़ाई को आधा कर देते थे। नया एल्गोरिदम इस समरूपता (symmetry) को तोड़ता है। स्थान को समान रूप से विभाजित करने के बजाय, यह प्रत्येक उपलब्ध स्लॉट को दो असमान बच्चों में विभाजित करता है: एक चौड़ा और एक संकरा। जब एक नया वर्ग (square) आता है, तो एल्गोरिदम यह निर्णय लेता है कि उसे इन असमान विभाजनों के सापेक्ष आकार के आधार पर कहाँ भेजना है। यदि कोई वर्ग संकीर्ण बच्चे के लिए बहुत बड़ा है, तो उसे चौड़े बच्चे में जाने के लिए मजबूर किया जाता है। यदि वह इतना छोटा है कि दोनों में फिट हो सके, तो एल्गोरिदम उसे उस बच्चे की ओर भेजता है जिसमें ब्लॉकों का वर्तमान स्टैक कम है। यह स्थानीय निर्णय लेने की प्रक्रिया, स्लॉट्स के पदानुक्रम के माध्यम से वर्ग के नीचे उतरने के साथ दोहराई जाती है, जिससे सिस्टम पुराने सममित (symmetric) तरीकों की तुलना में भार को अधिक प्रभावी ढंग से संतुलित कर पाता है।

यह सिद्ध करने के लिए कि यह रणनीति काम करती है, शोधकर्ताओं ने एक लेखांकन पद्धति का उपयोग किया जो रखे गए प्रत्येक वर्ग की "लागत" को ट्रैक करती है। उन्होंने कल्पना की कि प्रत्येक वर्ग अपनी ऊंचाई के लिए भुगतान करने हेतु अपने स्वयं के क्षेत्रफल को मुद्रा के रूप में उपयोग करता है। बड़े वर्ग, जिन्हें विशिष्ट स्लॉट्स में भेजा जाता है, अपनी ऊंचाई का भुगतान सीधे करते हैं। छोटे वर्ग, जिनके पास स्लॉट्स के बीच चयन करने का लचीलापन है, उन्हें समय के साथ संतुलन बनाने वाली अस्थायी क्रेडिट प्रणाली के माध्यम से संभाला जाता है। विश्लेषण से पता चलता है कि लचीले विकल्पों के कारण होने वाली दक्षता की हानि मीनार के ऊंचे होने के साथ जमा नहीं होती है; इसके बजाय, यह सीमित रहती है। यह गणितीय प्रमाण पुष्टि करता है कि एल्गोरिदम का प्रदर्शन स्थिर और अनुमानित है, चाहे ब्लॉकों का क्रम कुछ भी हो।

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

हालाँकि नया एल्गोरिदम एक महत्वपूर्ण प्रगति का प्रतिनिधित्व करता है, शोधकर्ता सावधानीपूर्वक यह उल्लेख करते हैं कि समस्या अभी भी पूरी तरह से हल नहीं हुई है। उन्होंने विशिष्ट परिदृश्य बनाए जहाँ उनका नया एल्गोरिदम एक ऐसी मीनार बनाता है जो इष्टतम ऑफलाइन समाधान से दोगुनी ऊँची है, जो यह दर्शाता है कि सर्वोत्तम संभव ऑनलाइन प्रदर्शन और सैद्धांतिक आदर्श के बीच का अंतर अभी भी काफी बड़ा है। लगभग 2.37 की नई ऊपरी सीमा और 2 की निचली सीमा के बीच का अंतर गणितज्ञों के लिए पाटने के लिए एक विस्तृत खाई है। हालाँकि, एक नया, तंग बाउंड (tighter bound) स्थापित करके और एक ऐसा ढांचा प्रदान करके जो वर्गों और सीमित आयतों दोनों को संभालता है, यह कार्य इस समस्या के परिदृश्य को स्पष्ट करता है। यह दिखाता है कि सही प्रकार के असममित संगठन के साथ, गुरुत्वाकर्षण की बाधाओं और भविष्य की अज्ञानता को पहले की तुलना में अधिक सटीकता के साथ प्रबंधित किया जा सकता है।

तकनीकी सारांश: टेट्रिस और ग्रेविटी के साथ ऑनलाइन स्क्वायर पैकिंग के लिए एक 2.37332-प्रतिस्पर्धी एल्गोरिदम

समस्या की परिभाषा
यह शोध पत्र टेट्रिस और ग्रेविटी बाधाओं (constraints) के तहत अक्षीय-समानांतर वर्गों (axis-parallel squares) के लिए ऑनलाइन स्ट्रिप पैकिंग समस्या को संबोधित करता है। इस मॉडल में, वर्ग बिना भविष्य की वस्तुओं की जानकारी के क्रमिक रूप से आते हैं और उन्हें अनंत ऊंचाई वाले एक इकाई-चौड़ाई (unit-width) के स्ट्रिप में अपरिवर्तनीय रूप से (irrevocably) रखा जाना चाहिए।

टेट्रिस बाधा (Tetris Constraint): एक आने वाले वर्ग को अपने अंतिम स्थान तक ऊपर से एक टकराव-मुक्त (collision-free), एकदिशीय (monotonic) नीचे की ओर पथ का पालन करना चाहिए।
ग्रेविटी बाधा (Gravity Constraint): वर्ग को स्ट्रिप के तल पर या पहले से रखे गए वर्गों की ऊपरी सतह पर टिकना चाहिए।
व्यवहार्यता (Feasibility): एक ज्यामितीय रूप से खाली क्षेत्र अनुपयोगी हो सकता है यदि वह नीचे की ओर जाने वाले पथ के माध्यम से अप्राप्य हो या उसमें सहारा (support) की कमी हो।

उद्देश्य कुल पैकिंग ऊंचाई को कम करना है। प्रदर्शन को अनंतस्पर्शी प्रतिस्पर्धी अनुपात (asymptotic competitive ratio - $CR$ ) द्वारा मापा जाता है, जिसे $\rho$ के इन्फिमम (infimum) के रूप में परिभाषित किया गया है जहाँ सभी इनपुट अनुक्रमों $\sigma$ के लिए $A(\sigma) \le \rho \cdot OPT(\sigma) + \beta$ है, जहाँ $A(\sigma)$ एल्गोरिदम की ऊंचाई है और $OPT(\sigma)$ इष्टतम ऑफलाइन ऊंचाई है।

कार्यप्रणाली: AsymmetricSlots
लेखक AsymmetricSlots नामक एक पुनरावर्ती (recursive) एल्गोरिदम प्रस्तुत करते हैं जो पिछले सर्वोत्तम ज्ञात दृष्टिकोण, SlotAlgorithm (Fekete et al., 2014) में सुधार करता है, जो एक द्वैदिक (dyadic/symmetric) पदानुक्रम का उपयोग करता था।

असममित पदानुक्रम (Asymmetric Hierarchy):
एक स्लॉट की चौड़ाई $w$ को दो समान भागों में विभाजित करने के बजाय, एल्गोरिदम इसे एक चौड़े बच्चे (wide child) की चौड़ाई $pw$ और एक संकीर्ण बच्चे (narrow child) की चौड़ाई $qw $में विभाजित करता है, जहाँ$ p \in (1/2, 1) $और$ q = 1-p$ है। यह पदानुक्रम किसी भी वस्तु के आने से पहले ही निर्धारित कर दिया जाता है।
स्थानीय रूटिंग नियम (Local Routing Rules):
आने पर, वर्तमान स्लॉट की चौड़ाई $w$ के सापेक्ष अपने आकार $a$ के आधार पर एक वर्ग नीचे की ओर जाता है:

प्रत्यक्ष (Direct): यदि $a > pw$, तो वर्ग को तुरंत वर्तमान स्लॉट के लिए आवंटित किया जाता है।
अनिवार्य (Forced): यदि $qw < a \le pw$ , तो वर्ग को चौड़े बच्चे में जाने के लिए मजबूर किया जाता है।
लचीला (Flexible): यदि $a \le qw$ , तो वर्ग को उस बच्चे की ओर निर्देशित किया जाता है जिसकी वर्तमान आभासी ऊंचाई (virtual height) कम है (टाई होने पर प्राथमिकता चौड़े बच्चे को दी जाती है)।

आभासी ऊंचाई प्रोफाइल और व्यवहार्यता (Virtual Height Profile & Feasibility):
एल्गोरिदम रूटिंग को निर्देशित करने के लिए एक खंडवार-स्थिर (piecewise-constant) आभासी ऊंचाई प्रोफाइल $h(x)$ बनाए रखता है। एक वर्ग जो स्लॉट $T$ को आवंटित किया गया है, वह अपने पक्ष की लंबाई $a$ द्वारा उस स्लॉट के अंतराल की आभासी ऊंचाई को अपडेट करता है।

लेम्मा 1 (Lemma 1) यह सिद्ध करता है कि आभासी प्रोफाइल द्वारा भौतिक ऊंचाई का अतिरंजित अनुमान लगाने के बावजूद, भौतिक प्रविष्टि (physical insertion) टेट्रिस और ग्रेविटी बाधाओं के तहत हमेशा व्यवहार्य होती है। विशेष रूप से, भौतिक वर्ग हमेशा एक समर्थन स्तर $y^*$ (जो मौजूदा वर्गों या स्ट्रिप तल द्वारा निर्धारित होता है) तक गिर सकता है जो आभासी अपडेट स्तर $\le$ है, जिससे नीचे की ओर जाने के दौरान कोई टकराव नहीं होता है।

स्थानीय चार्जिंग के माध्यम से विश्लेषण (Analysis via Local Charging):
प्रमाण एक स्थानीय चरण अपरिवर्तनीयता (local phase invariant) और एक चार्जिंग तर्क का उपयोग करता है जो विभाजन की विषमता का लाभ उठाता है:

अनिवार्य वर्ग (Forced Squares): बड़े वर्ग ($a > qw $) विशिष्ट पथों में मजबूर किए जाते हैं। उनका क्षेत्रफल उनके द्वारा बनाई गई ऊंचाई का भुगतान करने के लिए पर्याप्त है ($ wa - \rho a^2 \le 0$)।
लचीले वर्ग (Flexible Squares): छोटे वर्ग ( $a \le qw$ ) बच्चों के बीच संतुलन की अनुमति देते हैं। विश्लेषण एक "चरण-आधारित" (phase-based) लेखांकन का उपयोग करता है जहाँ एल्गोरिदम एक क्रेडिट $\delta w^2$ बनाए रखता है। विषमता यह सुनिश्चित करती है कि लचीले प्लेसमेंट से जुड़ा नुकसान स्थानीय रूप से सीमित रहता है और पदानुक्रम की गहराई के साथ संचित नहीं होता है।
चरण समापन (Phase Closure): एक चरण तब समाप्त होता है जब एक "प्रत्यक्ष" वर्ग (एक जो बच्चों के लिए बहुत बड़ा है) रखा जाता है, जो आभासी प्रोफाइल को रीसेट कर देता है।

मुख्य परिणाम

वर्गों के लिए बेहतर ऊपरी सीमा (Improved Upper Bound for Squares):
विभाजन पैरामीटर $p$ को अनुकूलित करके, लेखक 2.373318506... का प्रतिस्पर्धी अनुपात प्राप्त करते हैं।

इष्टतम पैरामीटर $p^\star$ , $16p^3 - 8p^2 + p - 1 = 0$ का $(1/2, 1)$ में अद्वितीय मूल है, जो $p^\star \approx 0.5786$ देता है।
परिणामी अनुपात $\rho^\star = 1/(1-p^\star) \approx 2.3733$ है।
$p = 11/19$ का एक परिमेय सन्निकटन (rational approximation) एक स्पष्ट अनुपात 2.375 ( $19/8$ ) प्रदान करता है।
यह Fekete et al. द्वारा स्थापित पूर्व सर्वोत्तम ऊपरी सीमा $34/13 \approx 2.6154$ में सुधार करता है।

एल्गोरिदम के लिए निचली सीमा (Lower Bound for the Algorithm):
यह शोध पत्र एक विशिष्ट निचली सीमा स्थापित करता है। बार-बार आने वाले वर्गों के निर्माण का उपयोग करते हुए, वे दिखाते हैं कि $p$ के एक रेंज के लिए जिसमें $p^\star$ शामिल है, प्रतिस्पर्धी अनुपात कम से कम 2 है।

इस प्रकार, $2 \le CR(AsymmetricSlots_{p^\star}) \le 2.3733...$
इस मॉडल में किसी भी नियतात्मक ऑनलाइन एल्गोरिदम के लिए सामान्य निचली सीमा अभी भी $3/2$ (Fekete et al. से) बनी हुई है।

आयतों (Rectangles) के लिए विस्तार:
इस ढांचे को एक सीमित पहलू अनुपात (aspect ratio) $\kappa$ वाले आयतों तक विस्तारित किया गया है (जहाँ चौड़ाई $u$ और ऊंचाई $v$ इस प्रकार है कि $u/\kappa \le v \le \kappa u$ )।

ऊपरी सीमा: एल्गोरिदम $O(\kappa)$ का अनंतस्पर्शी प्रतिस्पर्धी अनुपात प्राप्त करता है।
निचली सीमा: एक पतले ऊर्ध्वाधर और चौड़े उथले आयतों के वैकल्पिक निर्माण के माध्यम से एक मिलान $\Omega(\kappa)$ निचली सीमा सिद्ध की गई है।
यह स्थापित करता है कि पहलू अनुपात पर इष्टतम निर्भरता $\Theta(\kappa)$ है।

महत्व और दावे
यह शोध पत्र दावा करता है कि यह टेट्रिस और ग्रेविटी बाधाओं के साथ ऑनलाइन स्क्वायर पैकिंग समस्या के लिए सर्वोत्तम ज्ञात ऊपरी सीमा प्रदान करता है, जो प्रतिस्पर्धी अनुपात को $\approx 2.6154$ से घटाकर $\approx 2.3733$ कर देता है।

पद्धतिगत योगदान: सममित (द्वैदिक) से असममित पुनरावर्ती अपघटन (asymmetric recursive decomposition) की ओर बदलाव एक अधिक कुशल स्थानीय चार्जिंग तर्क की अनुमति देता है। विषमता "अनिवार्य" (बड़े) और "लचीले" (छोटे) प्लेसमेंट को अलग करती है, जिससे उन त्रुटि पदों का संचय रुक जाता है जो पिछले विश्लेषणों में समस्या पैदा करते थे।
क्षेत्र (Scope): परिणाम पूरी तरह से सैद्धांतिक हैं, जो भौतिक बाधाओं के तहत ऑनलाइन स्क्वायर पैकिंग के प्रतिस्पर्धी विश्लेषण पर केंद्रित हैं। यह शोध पत्र ऑफलाइन मामले के लिए सामान्य बहुपद-समय सन्निकटन योजना (polynomial-time approximation scheme) प्रदान करने का दावा नहीं करता है।
सीमाएं: लेखक नोट करते हैं कि एल्गोरिदम-विशिष्ट निचली सीमा (2) और ऊपरी सीमा (2.3733) के बीच का अंतर बना हुआ है, और सामान्य निचली सीमा (1.5) तथा ऊपरी सीमा के बीच भी अंतर है। यह शोध पत्र सुझाव देता है कि भविष्य के कार्य गैर-स्व-समान विभाजनों (non-self-similar splits) या दो से अधिक उप-स्लॉट्स का पता लगाकर इन अंतरालों को भरने के लिए खोज कर सकते हैं।

संक्षेप में, यह कार्य भौतिक बाधाओं के तहत ऑनलाइन स्क्वायर पैकिंग के सैद्धांतिक सीमाओं को परिष्कृत करता है, यह प्रदर्शित करता है कि असममित पदानुक्रमित अपघटन (asymmetric hierarchical decomposition) पिछले ज्ञात सममित दृष्टिकोणों की तुलना में बेहतर प्रतिस्पर्धी अनुपात प्रदान करता है।

इसी तरह के और पेपर