के-सर्वर समस्या
Is there a -competitive algorithm for solving the -server problem in an arbitrary metric space?
k-सर्वर समस्या ऑनलाइन एल्गोरिदम की श्रेणी में सैद्धांतिक कंप्यूटर विज्ञान की एक समस्या है, जो मीट्रिक रिक्त स्थान पर दो अमूर्त समस्याओं में से एक है जो प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम) के सिद्धांत के लिए केंद्रीय हैं (दूसरी मीट्रिक कार्य प्रणाली है)। इस समस्या में, एक ऑनलाइन एल्गोरिदम को k सर्वर के एक सेट की गति को नियंत्रित करना चाहिए, जो एक मीट्रिक स्थान में बिंदुओं के रूप में दर्शाया गया है, और अनुरोधों को संभालना चाहिए जो कि बिंदुओं के रूप में भी हैं अंतरिक्ष। जैसे ही प्रत्येक अनुरोध आता है, एल्गोरिदम को यह निर्धारित करना होगा कि किस सर्वर को अनुरोधित बिंदु पर ले जाना है। एल्गोरिदम का लक्ष्य सभी सर्वरों द्वारा स्थानांतरित की जाने वाली कुल दूरी को छोटा रखना है, यह उस कुल दूरी के सापेक्ष है जिसे सर्वर एक इष्टतम प्रतिद्वंद्वी द्वारा स्थानांतरित कर सकते हैं जो अनुरोधों के पूरे अनुक्रम को पहले से जानता है।
इस समस्या को सबसे पहले मार्क मनश्शे, लाइल ए. मैकगियोच और डेनियल स्लेटर (1988) ने सामने रखा था।[1] के-सर्वर समस्या से संबंधित सबसे प्रमुख खुला प्रश्न तथाकथित के-सर्वर अनुमान है, जिसे मनसे एट अल द्वारा भी प्रस्तुत किया गया है। यह अनुमान बताता है कि एक मनमाना मीट्रिक स्थान में k-सर्वर समस्या को हल करने के लिए और किसी भी संख्या k सर्वर के लिए एक एल्गोरिदम है जिसका प्रतिस्पर्धी अनुपात बिल्कुल k है। मनस्से एट अल. जब k = 2 था, तब वे अपने अनुमान को साबित करने में सक्षम थे, और कुछ मीट्रिक स्थानों के लिए k के अधिक सामान्य मानों के लिए बिल्कुल k+1 अंक तक सीमित थे। मार्क क्रोबक और लॉरेंस एल. लारमोर (1991) ने वृक्ष मेट्रिक्स के अनुमान को साबित किया। मेट्रिक्स का विशेष मामला जिसमें सभी दूरियां समान होती हैं, पेजिंग समस्या कहलाती है क्योंकि यह मेमोरी कैश में पेज प्रतिस्थापन एल्गोरिदम की समस्या को मॉडल करती है, और यह पहले से ही ज्ञात था k-प्रतिस्पर्धी एल्गोरिदम (डैनियल स्लेटर और रॉबर्ट टार्जन 1985)। फिएट एट अल. (1990) ने पहली बार साबित किया कि किसी भी स्थिरांक k और किसी भी मीट्रिक स्थान के लिए परिमित प्रतिस्पर्धी अनुपात के साथ एक एल्गोरिदम मौजूद है, और अंत में कौट्सोपियास और क्रिस्टोस पापादिमित्रियोउ (1995) ने साबित किया कि वर्क फंक्शन एल्गोरिदम (डब्ल्यूएफए) में प्रतिस्पर्धी अनुपात 2k - 1 है। कई अन्य शोधकर्ताओं के प्रयासों ने प्रतिस्पर्धी अनुपात को कम कर दिया है k या एक बेहतर निचली सीमा प्रदान करना खुला रहता है as of 2014[update]. सबसे आम माना जाने वाला परिदृश्य यह है कि कार्य फ़ंक्शन एल्गोरिदम k-प्रतिस्पर्धी है। इस दिशा में, 2000 में बार्टल और कौट्सोपियास ने दिखाया कि यह कुछ विशेष मामलों के लिए सच है (यदि मीट्रिक स्थान एक रेखा, एक भारित तारा या k+2 बिंदुओं का कोई मीट्रिक है)।
2011 में, प्रतिस्पर्धी बाध्य Õ(लॉग) के साथ एक यादृच्छिक एल्गोरिदम2k लॉग3n) पाया गया.[2][3] 2017 में, प्रतिस्पर्धी बाध्य ओ (लॉग) के साथ एक यादृच्छिक एल्गोरिदम6k) की घोषणा की गई,[4] लेकिन बाद में वापस ले लिया गया।[5] 2022 में यह दिखाया गया कि अनुमान सामान्य तौर पर गलत है।[6]
उदाहरण
समस्या को और अधिक ठोस बनाने के लिए, ग्राहकों को उनके उपकरण में समस्या होने पर ग्राहक सहायता तकनीशियनों को भेजने की कल्पना करें। हमारी उदाहरण समस्या में दो तकनीशियन हैं, मैरी और नूह, सैन फ्रांसिस्को, कैलिफ़ोर्निया में तीन ग्राहकों को सेवा दे रहे हैं; वाशिंगटन डीसी; और बाल्टीमोर, मैरीलैंड। के-सर्वर समस्या के रूप में, सर्वर तकनीशियन हैं, इसलिए के = 2 और यह 2-सर्वर समस्या है। वाशिंगटन और बाल्टीमोर हैं 35 miles (56 km) अलग, जबकि सैन फ्रांसिस्को है 3,000 miles (4,800 km) दोनों से दूर, और शुरुआत में मैरी और नूह दोनों सैन फ्रांसिस्को में हैं।
अनुरोधों के लिए सर्वर निर्दिष्ट करने के लिए एक एल्गोरिदम पर विचार करें जो हमेशा अनुरोध के लिए निकटतम सर्वर निर्दिष्ट करता है, और मान लें कि प्रत्येक कार्यदिवस की सुबह वाशिंगटन में ग्राहक को सहायता की आवश्यकता होती है जबकि प्रत्येक कार्यदिवस दोपहर को बाल्टीमोर में ग्राहक को सहायता की आवश्यकता होती है, और सैन फ्रांसिस्को में ग्राहक को कभी भी सहायता की आवश्यकता नहीं होती है सहायता। फिर, हमारा एल्गोरिदम सर्वरों में से एक (जैसे मैरी) को वाशिंगटन क्षेत्र में नियुक्त करेगा, जिसके बाद वह हमेशा निकटतम सर्वर रहेगा और हमेशा सभी ग्राहक अनुरोधों के लिए उसे सौंपा जाएगा। इस प्रकार, हर दिन हमारा एल्गोरिदम वाशिंगटन और बाल्टीमोर के बीच और वापसी की यात्रा की लागत वहन करता है, 70 miles (110 km). इस अनुरोध पैटर्न के एक वर्ष के बाद, एल्गोरिथम खर्च हो जाएगा 20,500 miles (33,000 km) यात्रा: मैरी को पूर्वी तट पर भेजने के लिए 3,000, और वाशिंगटन और बाल्टीमोर के बीच यात्रा के लिए 17,500। दूसरी ओर, एक इष्टतम प्रतिद्वंद्वी जो भविष्य के अनुरोध कार्यक्रम को जानता है, वह मैरी और नूह दोनों को भुगतान करके क्रमशः वाशिंगटन और बाल्टीमोर भेज सकता था। 6,000 miles (9,700 km) एक बार यात्रा करें लेकिन फिर भविष्य की किसी भी यात्रा लागत से बचें। इस इनपुट पर हमारे एल्गोरिदम का प्रतिस्पर्धी अनुपात 20,500/6,000 या लगभग 3.4 है, और इस उदाहरण के मापदंडों को समायोजित करके इस एल्गोरिदम के प्रतिस्पर्धी अनुपात को मनमाने ढंग से बड़ा बनाया जा सकता है।
इस प्रकार हम देखते हैं कि हमेशा निकटतम सर्वर निर्दिष्ट करना इष्टतम से बहुत दूर हो सकता है। दूसरी ओर, यह एक ऐसे एल्गोरिदम के लिए मूर्खतापूर्ण लगता है जो अपने दोनों तकनीशियनों को सैन फ्रांसिस्को से दूर भेजने के भविष्य के अनुरोधों को नहीं जानता है, क्योंकि अगला अनुरोध उस शहर में हो सकता है और उसे तुरंत किसी को वापस भेजना होगा। तो ऐसा लगता है कि के-सर्वर एल्गोरिदम के लिए अपने प्रतिद्वंद्वी के सापेक्ष अच्छा प्रदर्शन करना मुश्किल या असंभव है। हालाँकि, 2-सर्वर समस्या के लिए, एक एल्गोरिथ्म मौजूद है जिसकी कुल यात्रा दूरी हमेशा प्रतिद्वंद्वी की दूरी से दोगुनी होती है। के-सर्वर अनुमान बताता है कि बड़ी संख्या में तकनीशियनों की समस्याओं के लिए समान समाधान मौजूद हैं।
संदर्भ
- ↑ Manasse, Mark; McGeoch, Lyle; Sleator, Daniel (1988-01-01). "ऑनलाइन समस्याओं के लिए प्रतिस्पर्धी एल्गोरिदम". Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC '88. New York, NY, USA: Association for Computing Machinery: 322–333. doi:10.1145/62212.62243. ISBN 978-0-89791-264-8. S2CID 13356897.
- ↑ Bansal, Nikhil; Buchbinder, Niv; Madry, Aleksander; Naor, Joseph (2015). "A polylogarithmic-competitive algorithm for the k[[Category: Templates Vigyan Ready]]-server problem" (PDF). Journal of the ACM. 62 (5): A40:1–A40:49. arXiv:1110.1580. doi:10.1145/2783434. MR 3424197. S2CID 15668961.
{{cite journal}}: URL–wikilink conflict (help) - ↑ "एक और कष्टप्रद खुली समस्या". 19 November 2011.
- ↑ [1] which closely built on [2]
- ↑ "Erratum: Fusible HSTS and the randomized k-server conjecture".
- ↑ Bubeck, Sébastien; Coester, Christian; Rabani, Yuval (2022). "यादृच्छिक के-सर्वर अनुमान गलत है". arXiv:2211.05753 [cs.DS].
- Chrobak, Marek; Larmore, Lawrence L. (1991). "An optimal on-line algorithm for K-servers on trees". SIAM Journal on Computing. 20 (1): 144–148. CiteSeerX 10.1.1.53.2395. doi:10.1137/0220008.
- Fiat, A.; Rabani, Y.; Ravid, Y. (1990). "Competitive k-server algorithms". Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science. pp. 454–463.
- Koutsoupias, Elias; Papadimitriou, Christos H. (1995). "On the k-server conjecture". Journal of the ACM. 42 (5): 971–983. doi:10.1145/210118.210128. S2CID 5813837.
- Manasse, Mark; McGeoch, Lyle A.; Sleator, Daniel D. (1990). "Competitive algorithms for server problems". Journal of Algorithms. 11 (2): 208–230. doi:10.1016/0196-6774(90)90003-W.
- Sleator, Daniel D.; Tarjan, Robert E. (1985). "Amortized efficiency of list update and paging rules". Communications of the ACM. 28 (2): 202–208. doi:10.1145/2786.2793. S2CID 2494305.
