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

ऑनलाइन एल्गोरिदम को इनपुट आने पर अपरिवर्तनीय निर्णय लेने होते हैं, भविष्य के अनुरोधों के ज्ञान के बिना; उनकी गुणवत्ता का मूल्यांकन एक इष्टतम एल्गोरिदम के खिलाफ प्रतिस्पर्धी विश्लेषण द्वारा किया जाता है जो पूरे इनपुट को पहले से देखता है।

Definition

एक ऑनलाइन एल्गोरिदम अनुरोधों के अनुक्रम के रूप में अपना इनपुट प्राप्त करता है और भविष्य के अनुरोधों को देखे बिना प्रत्येक पर तुरंत और अपरिवर्तनीय रूप से प्रतिक्रिया देनी होती है; इसका प्रतिस्पर्धी अनुपात इसकी लागत का एक इष्टतम ऑफ़लाइन एल्गोरिदम की लागत का सबसे खराब स्थिति वाला अनुपात है जो पूरे अनुरोध अनुक्रम को जानता है।

Scope

यह विषय उन एल्गोरिदम को शामिल करता है जो इनपुट को क्रमिक रूप से संसाधित करते हैं और बाद में इनपुट ज्ञात होने से पहले निर्णयों के लिए प्रतिबद्ध होते हैं, और प्रतिस्पर्धी-अनुपात ढांचा जिसका उपयोग उन्हें एक इष्टतम ऑफ़लाइन विरोधी के खिलाफ मूल्यांकन करने के लिए किया जाता है। इसमें क्लासिक समस्याएं शामिल हैं — पेजिंग और कैशिंग, सूची अद्यतन, स्की-रेंटल समस्या, k-सर्वर समस्या, और ऑनलाइन शेड्यूलिंग और बिन पैकिंग — और कमजोर विरोधियों के खिलाफ प्रतिस्पर्धी अनुपातों में सुधार में यादृच्छिकीकरण की भूमिका।

Core questions

• भविष्य अज्ञात होने पर ऑनलाइन एल्गोरिदम का मूल्यांकन कैसे किया जाता है?
• प्रतिस्पर्धी अनुपात क्या मापता है, और ऑफ़लाइन विरोधी क्या है?
• पेजिंग और स्की रेंटल जैसी क्लासिक समस्याएं ऑनलाइन ट्रेड-ऑफ को कैसे दर्शाती हैं?
• एक अनभिज्ञ विरोधी के खिलाफ यादृच्छिकीकरण प्रतिस्पर्धात्मकता में कैसे सुधार कर सकता है?
• कौन सी निचली सीमाएं किसी भी ऑनलाइन एल्गोरिदम की प्रतिस्पर्धात्मकता को सीमित करती हैं?

Key concepts

• ऑनलाइन बनाम ऑफ़लाइन
• प्रतिस्पर्धी अनुपात
• ऑफ़लाइन विरोधी
• पेजिंग और कैशिंग
• सूची अद्यतन
• स्की-रेंटल समस्या
• k-सर्वर समस्या
• यादृच्छिक प्रतिस्पर्धात्मकता

Key theories

प्रतिस्पर्धी विश्लेषण

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

अनभिज्ञ विरोधियों के खिलाफ यादृच्छिकीकरण

यादृच्छिक ऑनलाइन एल्गोरिदम एक अनभिज्ञ विरोधी के खिलाफ किसी भी नियतात्मक एल्गोरिदम की तुलना में सख्ती से बेहतर प्रतिस्पर्धी अनुपात प्राप्त कर सकते हैं, क्योंकि विरोधी को एल्गोरिदम के यादृच्छिक विकल्पों को जाने बिना इनपुट को ठीक करना होगा।

Clinical relevance

ऑनलाइन एल्गोरिदम उन निर्णयों को मॉडल करते हैं जो सिस्टम भविष्य के ज्ञान के बिना वास्तविक समय में लेते हैं: ऑपरेटिंग सिस्टम और सीपीयू में कैश और पेज प्रतिस्थापन, डेटा-संरचना स्व-संगठन, गतिशील संसाधन आवंटन और लोड संतुलन, और क्लाउड कंप्यूटिंग में किराए पर लेने या खरीदने के निर्णय। प्रतिस्पर्धी विश्लेषण ऐसे प्रतिक्रियाशील प्रणालियों के लिए सबसे खराब स्थिति की गारंटी देता है।

History

प्रतिस्पर्धी विश्लेषण को स्लेटर और टार्जन ने 1985 में सूची-अद्यतन और पेजिंग नियमों के अपने अध्ययन के माध्यम से प्रस्तुत किया था, जिसमें ऑनलाइन एल्गोरिदम के मूल्यांकन को एक इष्टतम ऑफ़लाइन समाधान के साथ तुलना के इर्द-गिर्द फिर से तैयार किया गया था। यह ढांचा 1990 के दशक में k-सर्वर समस्या और यादृच्छिक ऑनलाइन एल्गोरिदम के माध्यम से विस्तारित हुआ, जिसका सर्वेक्षण बोरोडिन और एल-यानिव के 1998 के मोनोग्राफ में किया गया था।

Key figures

• Daniel Sleator
• Robert Tarjan
• Allan Borodin
• Ran El-Yaniv

Seminal works

• sleator1985
• borodin1998
• cormen2009

Frequently asked questions

प्रतिस्पर्धी अनुपात क्या है?

यह एक ऑनलाइन एल्गोरिदम की लागत का एक इष्टतम एल्गोरिदम की लागत का सबसे खराब स्थिति वाला अनुपात है जो पूरे इनपुट को पहले से देखता है। एक 2-प्रतिस्पर्धी एल्गोरिदम किसी भी इनपुट अनुक्रम पर सर्वोत्तम संभव ऑफ़लाइन लागत से दोगुना से अधिक कभी नहीं होता है।

यादृच्छिकीकरण ऑनलाइन एल्गोरिदम की मदद क्यों करता है?

एक अनभिज्ञ विरोधी के खिलाफ जो एल्गोरिदम के यादृच्छिक विकल्पों को देखे बिना इनपुट को ठीक करता है, यादृच्छिकीकरण विरोधी को एल्गोरिदम के व्यवहार के लिए सबसे खराब स्थिति को अनुकूलित करने से रोकता है, जिससे किसी भी नियतात्मक एल्गोरिदम की तुलना में सख्ती से बेहतर प्रतिस्पर्धी अनुपात प्राप्त होता है।