तकनीकी सारांश: स्टोकेस्टिक आगमन के साथ ऑनलाइन नॉन-सेंट्रॉइड क्लस्टरिंग में विलंबित असाइनमेंट

1. समस्या की परिभाषा

यह शोध पत्र ऑनलाइन नॉन-सेंट्रॉइड क्लस्टरिंग विद डिलेज़ (OCD) समस्या को प्रस्तुत करता है और इसका अध्ययन करता है। यह समस्या क्लासिक क्लस्टरिंग प्रतिमान (paradigm) का विस्तार करती है जहाँ तत्व (बिंदु) एक परिमित मीट्रिक स्पेस $M = (X, d)$ में अनुक्रमिक रूप से आते हैं।

मुख्य विशेषताएँ:

• नॉन-सेंट्रॉइड क्लस्टरिंग: सेंटर-आधारित क्लस्टरिंग (जैसे k-means) के विपरीत, यहाँ क्लस्टर किसी केंद्रीय बिंदु द्वारा परिभाषित नहीं होते हैं। इसके बजाय, उद्देश्य एक ही क्लस्टर के भीतर सभी बिंदुओं के बीच युग्मवार (pairwise) दूरियों के योग को कम करना है। यह उन परिदृश्यों को मॉडल करता है जैसे टीम निर्माण या राइड-शेयरिंग, जहाँ एजेंट अपने समूह के सभी सदस्यों के निकटता को प्राथमिकता देते हैं, न कि केवल एक नेता को।
• निश्चित-आकार की बाधाएँ (Fixed-Size Constraints): शोध पत्र पूर्व-निर्धारित क्लस्टर आकार $\{n_m\}_{m \in [k]}$ के साथ क्लस्टरिंग पर ध्यान केंद्रित करता है जहाँ $\sum n_m = n$ है। यह साधारण समाधानों (जैसे सिंगलटन) से बचने में मदद करता है और वास्तविक दुनिया की क्षमता सीमाओं (जैसे वाहन की सीमा, टीम का आकार) को दर्शाता है।
• विलंबित असाइनमेंट (Delayed Assignments): समय $t_i$ पर आगमन के समय, एक बिंदु का स्थान $\ell_i$ प्रकट किया जाता है। एल्गोरिदम बिंदु को तुरंत असाइन करने के लिए मजबूर नहीं है। यह असाइनमेंट को बाद के समय $s_i \ge t_i$ तक टाल सकता है, जिससे एक विलंब लागत (delay cost) $w_i = s_i - t_i$ उत्पन्न होती है।
• लागत फलन (Cost Function): क्लस्टरिंग की कुल लागत कनेक्शन लागत (क्लस्टर के भीतर युग्मवार दूरियाँ) और विलंब लागत का योग है। महत्वपूर्ण रूप से, एक एकल बिंदु की विलंब लागत उसके क्लस्टर के अन्य सभी सदस्यों की कनेक्शन लागत को प्रभावित करती है (उदाहरण के लिए, गेमिंग में, एक खिलाड़ी का इंतज़ार पूरे समूह की शुरुआत में देरी करता है)। एक ही क्लस्टर में मौजूद जोड़ी $i, j$ के लिए लागत $d(\ell_i, \ell_j) + w_i + w_j$ है।
• स्टोकेस्टिक आगमन मॉडल: शोध पत्र अननोन i.i.d. (UIID) मॉडल के तहत कार्य करता है। बिंदु एक अज्ञात, स्थिर संभाव्यता वितरण (probability distribution) से समय के साथ स्वतंत्र रूप से आते हैं। यह क्लासिक वर्स्ट-केस (एडवर्सरियल) मॉडल के विपरीत है, जहाँ इस समस्या के लिए कोई ऑनलाइन एल्गोरिदम निरंतर प्रतिस्पर्धी अनुपात (constant competitive ratio) प्राप्त नहीं कर सकता है।

प्रदर्शन मीट्रिक:
एल्गोरिदम के प्रदर्शन को रेशियो-ऑफ-एक्सपेक्टेशन्स (RoE) द्वारा मापा जाता है। एक एल्गोरिदम $A$ तब $c$-प्रतिस्पर्धी (c-competitive) होता है यदि:
$$\text{RoE}(A) = \lim_{n \to \infty} \frac{\mathbb{E}[\text{Cost}(A)]}{\mathbb{E}[\text{Cost}(\text{OPT})]} \le c$$
जहाँ प्रत्याशा (expectation) रैंडम आगमन अनुक्रम और एल्गोरिदम की आंतरिक रैंडमनेस पर ली जाती है।

2. कार्यप्रणाली: DGREEDY एल्गोरिदम

लेखक एक DGREEDY (डिलेड ग्रीडी) नामक एक नियतात्मक (deterministic), ग्रीडी एल्गोरिदम प्रस्तावित करते हैं। एल्गोरिदम प्रत्येक समय चरण $t$ पर बिंदुओं को प्रोसेस करता है, जिसमें नए आए बिंदुओं और "लंबित" (pending) बिंदुओं (वे जो अभी तक असाइन नहीं किए गए हैं) दोनों पर विचार किया जाता है।

एल्गोरिदम का तर्क:
किसी भी लंबित बिंदु $i$ के लिए, DGREEDY दो संभावित कार्यों के सेट की पहचान करता है:

1. मौजूदा क्लस्टर ($S_i$): मौजूदा क्लस्टरों $C_m$ का सेट जो अभी भरे नहीं हैं ($|C_m| < n_m$) और एक ज्यामितीय शर्त को पूरा करते हैं: $i$ की किसी सदस्य $j \in C_m$ से दूरी, $i$ के प्रतीक्षा समय और $j$ की विलंब लागत के बराबर या उससे कम है ($d(\ell_i, \ell_j) \le (t - t_i) + w_j$)।
2. लंबित जोड़े ($D_i$): यदि कम से कम दो लंबित बिंदु हैं, तो एल्गोरिदम एक खाली क्लस्टर स्लॉट में एक जोड़ी $(i, j)$ के साथ नया क्लस्टर बनाने पर विचार करता है, बशर्ते कि उनका संयुक्त प्रतीक्षा समय उनकी दूरी से अधिक हो ($d(\ell_i, \ell_j) \le (t - t_i) + (t - t_j)$)।

निर्णय नियम:

• यदि $S_i$ गैर-रिक्त है, तो एल्गोरिदम उस क्लस्टर $m_1$ को चुनता है जो कुल लागत में वृद्धि को न्यूनतम करता है।
• यदि $D_i$ गैर-रिक्त है, तो यह उस जोड़ी $(j, m_2)$ को चुनता है जो लागत वृद्धि को न्यूनतम करती है, और टाई होने पर जोड़ी की कुल प्रतीक्षा समय को अधिकतम करके निर्णय लेता है (ताकि लागत अनिश्चित काल तक न बढ़े)।
• अंतिम असाइनमेंट: एल्गोरिदम सबसे अच्छे मौजूदा क्लस्टर विकल्प ($m_1$) और सबसे अच्छे नए जोड़े के विकल्प ($m_2$) की तुलना करता है। यह उस असाइनमेंट को निष्पादित करता है जो कम कुल लागत वृद्धि देता है। यदि दोनों में से कोई भी नहीं चुना जाता है, तो बिंदु $i$ प्रतीक्षा करना जारी रखता है।

ज्यामितीय व्याख्या:
एल्गोरिदम को लंबित बिंदुओं के केंद्र वाले विस्तार होते हुए बॉल्स (balls) के रूप में देखा जा सकता है। एक बॉल की त्रिज्या समय के साथ बढ़ती है (जो विलंब लागत को दर्शाती है)। एक असाइनमेंट तब होता है जब एक लंबित बिंदु की बॉल, मौजूदा क्लस्टर के किसी बिंदु या दूसरे लंबित बिंदु की बॉल के साथ प्रतिच्छेद (intersect) करती है।

3. मुख्य योगदान और परिणाम

सैद्धांतिक गारंटी

प्राथमिक योगदान यह प्रमाण है कि DGREEDY, UIID मॉडल के तहत एक निरंतर Ratio-of-Expectations प्राप्त करता है।

• DGREEDY पर ऊपरी सीमा (Upper Bound): लेखक DGREEDY की अपेक्षित कुल लागत पर एक ऊपरी सीमा निर्धारित करते हैं। वे बिंदुओं को "अर्ली" (early) और "लेट" (late) बिंदुओं में वर्गीकृत करते हैं, जो उनके आगमन के एक विशिष्ट रेडियस $r_x$ (जो वितरण और मीट्रिक गुणों द्वारा परिभाषित है) के भीतर असाइन किए गए हैं या नहीं, इस पर आधारित है।

  • अर्ली पॉइंट्स: उनकी विलंबता $r_x$ द्वारा सीमित है।
  • लेट पॉइंट्स: उनकी विलंबता मीट्रिक स्पेस के व्यास (diameter) द्वारा सीमित है, लेकिन लेखक सिद्ध करते हैं कि ऐसे अधिकतम $|X|$ (परिमित) बिंदु हैं।
  • कुल अपेक्षित लागत $O(n)$ दिखाई गई है।

• OPT पर निचली सीमा (Lower Bound): लेखक अनुकूलतम ऑफलाइन समाधान (OPT) की अपेक्षित लागत पर एक निचली सीमा स्थापित करते हैं। वे प्रत्येक बिंदु के लिए न्यूनतम लागत $c_i(\sigma)$ का विश्लेषण करते हैं, यह दिखाते हुए कि स्टोकेस्टिक सेटिंग में, प्रत्येक बिंदु के लिए अपेक्षित न्यूनतम लागत उसके स्थानीय पड़ोस के संभाव्यता द्रव्यमान (probability mass) के व्युत्क्रमानुपाती होती है। यह $O(n)$ निचली सीमा भी प्रदान करता है।

• निरंतर प्रतिस्पर्धी अनुपात (Constant Competitive Ratio): DGREEDY की ऊपरी सीमा और OPT की निचली सीमा की तुलना करके, लेखक सिद्ध करते हैं कि:
  $$\lim_{n \to \infty} \frac{\text{DGREEDY}(I)}{\text{OPT}(I)} \le \frac{8(n_1 - 1)}{(n_k - 1)(1 - e^{-2})}$$
  यदि सभी क्लस्टर आकार समान हैं ($n_m = n'$), तो अनुपात सरल होकर एक स्थिरांक बन जाता है:
  $$\lim_{n \to \infty} \frac{\text{DGREEDY}(I)}{\text{OPT}(I)} \le \frac{8}{1 - e^{-2}} \approx 12.5$$
  यह परिणाम दर्शाता है कि, वर्स्ट-केस मॉडल के विपरीत जहाँ प्रतिस्पर्धी अनुपात सब-लॉगैरिद्मिक या अनबाउंडेड होता है, स्टोकेस्टिक मॉडल निरंतर-प्रतिस्पर्धी एल्गोरिदम की अनुमति देता है।

विस्तार (Extensions)

शोध पत्र प्रदर्शित करता है कि सैद्धांतिक ढांचा निम्नलिखित पर भी लागू होता है:

1. नॉन-मीट्रिक स्पेस: एल्गोरिदम और विश्लेषण एसिमेट्रिक दूरियों (सिमेट्राइजेशन के माध्यम से) और नॉन-ट्राइएंगल इनइक्वेलिटी स्पेस (शॉर्टेस्ट-पाथ मीट्रिक के माध्यम से) के लिए भी मान्य हैं।
2. हेडोनिक गेम्स: यह मॉडल एजेंट प्रकारों के साथ ऑनलाइन एडिटिवली सेपरेबल हेडोनिक गेम्स (ASHGs) में सीधे मैप होता है, जहाँ एजेंटों की गठबंधन सदस्यों के प्रति प्राथमिकताएं होती हैं।
3. परिवर्तनीय क्लस्टर आकार: परिणाम उन मामलों में भी विस्तारित होते हैं जहाँ क्लस्टर आकार के निचले और ऊपरी बाउंड ($l_m \le |C_m| \le u_m$) होते हैं, बशर्ते कि बाउंड्स स्थिरांक (constants) हों।

4. महत्व और दावे

शोध पत्र का दावा है कि यह "वर्स्ट-केस एडवर्सरीज से परे जाने की उम्मीद" प्रदान करता है। इसका महत्व निम्नलिखित में निहित है:

• एक अंतर को भरना: यह 'विलंब के साथ ऑनलाइन नॉन-सेंट्रॉइड क्लस्टरिंग' पर शोध की कमी को संबोधित करता है, जो गेमिंग, राइड-शेयरिंग और फेडेरेटेड लर्निंग जैसे वास्तविक दुनिया के अनुप्रयोगों के लिए प्रासंगिक है।
• असंभवता को पार करना: यह दिखाता है कि वर्स्ट-केस मॉडल की मजबूत असंभवता के परिणामों (जहाँ कोई निरंतर प्रतिस्पर्धी अनुपात मौजूद नहीं है) को एक स्टोकेस्टिक आगमन प्रक्रिया (UIID) मानकर दरकिनार किया जा सकता है।
• व्यावहारिक प्रासंगिकता: $n \to \infty$ के रूप में रेश्यो-ऑफ-एक्सपेक्टेशन्स पर ध्यान केंद्रित करके, शोध पत्र छोटे, पैथोलॉजिकल वर्स्ट-केस इनपुट के बजाय बड़े पैमाने के, व्यावहारिक परिदृश्यों को लक्षित करता है।
• एल्गोरिदम की सरलता: प्रस्तावित DGREEDY एल्गोरिदम नियतात्मक और ग्रीडी है, जो यह सुझाव देता है कि इस स्टोकेस्टिक सेटिंग में निरंतर प्रतिस्पर्धात्मकता प्राप्त करने के लिए जटिल संभावabilistic या लर्निंग-आधारित दृष्टिकोणों की आवश्यकता नहीं हो सकती है।

लेखक निष्कर्ष निकालते हैं कि उनका कार्य सामान्य विलंब लागत फलनों (delay cost functions), ज्ञात या समय-परिवर्तित वितरणों, और उन सेटिंग्स में भविष्य के अनुसंधान का मार्ग प्रशस्त करता है जहाँ दंड (penalties) के साथ क्लस्टरिंग को संशोधित किया जा सकता है।