के-सर्वर समस्या
Is there a -competitive algorithm for solving the -server problem in an arbitrary metric space?
k-सर्वर समस्या ऑनलाइन एल्गोरिदम की श्रेणी में सैद्धांतिक कंप्यूटर विज्ञान की समस्या है, जो मीट्रिक रिक्त स्थान पर दो संक्षेप समस्याओं में से एक है जो प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम) के सिद्धांत के लिए केंद्रीय हैं (दूसरी मीट्रिक कार्य प्रणाली है)। इस समस्या में, ऑनलाइन एल्गोरिदम को k सर्वर के सेट की गति को नियंत्रित करना चाहिए, जो मीट्रिक स्पेस में बिंदुओं के रूप में दर्शाया गया है, और अनुरोधों को संभालना चाहिए जो कि बिंदुओं के रूप स्पेस में हैं। जैसे ही प्रत्येक अनुरोध आता है, एल्गोरिदम को यह निर्धारित करना होगा कि किस सर्वर को अनुरोधित बिंदु पर ले जाना है। एल्गोरिदम का लक्ष्य सभी सर्वरों द्वारा स्थानांतरित की जाने वाली कुल दूरी को छोटा रखना है, यह उस कुल दूरी के सापेक्ष है जिसे सर्वर विरोधी भूमिका द्वारा स्थानांतरित कर सकते हैं जो अनुरोधों के पूरे अनुक्रम को पहले से जानता है।
इस समस्या को सबसे पहले मार्क मनश्शे, लाइल ए. मैकगियोच और डेनियल स्लेटर (1988) ने सामने रखा था।[1] k-सर्वर समस्या से संबंधित सबसे प्रमुख खुला प्रश्न तथाकथित k-सर्वर अनुमान है, जिसे मनसे एट अल द्वारा भी प्रस्तुत किया गया है। यह अनुमान बताता है कि अपने ढंग से मीट्रिक स्पेस में 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 में, प्रतिस्पर्धी बाध्य Õ(log2k log3n) के साथ यादृच्छिक एल्गोरिदम पाया गया है।[2][3] 2017 में, प्रतिस्पर्धी बाध्य O(log6k) के साथ यादृच्छिक एल्गोरिदम की घोषणा की गई,[4] परन्तु बाद में वापस ले लिया गया है।[5] 2022 में यह दिखाया गया कि अनुमान सामान्य तौर पर गलत है।[6]
उदाहरण
समस्या को और अधिक ठोस बनाने के लिए, ग्राहकों को उनके उपकरण में समस्या होने पर ग्राहक सहायता तकनीशियनों को भेजने की कल्पना करते हैं। हमारी उदाहरण समस्या में दो तकनीशियन हैं, मैरी और नूह, सैन फ्रांसिस्को, कैलिफ़ोर्निया में तीन ग्राहकों वाशिंगटन डीसी; और बाल्टीमोर, मैरीलैंड को सेवा दे रहे हैं; k-सर्वर समस्या के रूप में, सर्वर तकनीशियन हैं, इसलिए k = 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 है, और इस उदाहरण के मापदंडों को समायोजित करके इस एल्गोरिदम के प्रतिस्पर्धी अनुपात को मनमाने ढंग से बड़ा बनाया जा सकता है।
इस प्रकार हम देखते हैं कि हमेशा निकटतम सर्वर निर्दिष्ट करना सर्वोत्तम से बहुत दूर हो सकता है। दूसरी ओर, यह ऐसे एल्गोरिदम के लिए मूर्खतापूर्ण लगता है जो अपने दोनों तकनीशियनों को सैन फ्रांसिस्को से दूर भेजने के भविष्य के अनुरोधों को नहीं जानता है, क्योंकि अगला अनुरोध उस शहर में हो सकता है और उसे तुरंत किसी को वापस भेजना होगा। तो ऐसा लगता है कि k-सर्वर एल्गोरिदम के लिए अपने विरोधी के सापेक्ष अच्छा प्रदर्शन करना कठिन या असंभव है। चूँकि, 2-सर्वर समस्या के लिए, एल्गोरिथ्म उपस्थित है जिसकी कुल यात्रा दूरीलगभग विरोधी की दूरी से दोगुनी होती है। k-सर्वर अनुमान बताता है कि बड़ी संख्या में तकनीशियनों की समस्याओं के लिए समान समाधान उपस्थित हैं।
संदर्भ
- ↑ 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.
