View source for के-सर्वर समस्या

{{Short description|Computational problem of interest in computer science}}
{{DISPLAYTITLE:''k''-server problem}}{{unsolved|computer science|Is there a <math>k</math>-competitive algorithm for solving the <math>k</math>-server problem in an arbitrary metric space?}}
{{var|k}}-सर्वर समस्या [[ऑनलाइन एल्गोरिदम]] की श्रेणी में [[सैद्धांतिक कंप्यूटर विज्ञान]] की एक समस्या है, जो मीट्रिक रिक्त स्थान पर दो अमूर्त समस्याओं में से एक है जो [[प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)]] के सिद्धांत के लिए केंद्रीय हैं (दूसरी [[मीट्रिक कार्य प्रणाली]] है)। इस समस्या में, एक ऑनलाइन एल्गोरिदम को ''k'' ''सर्वर'' के एक सेट की गति को नियंत्रित करना चाहिए, जो एक [[मीट्रिक स्थान]] में बिंदुओं के रूप में दर्शाया गया है, और ''अनुरोधों'' को संभालना चाहिए जो कि बिंदुओं के रूप में भी हैं अंतरिक्ष। जैसे ही प्रत्येक अनुरोध आता है, एल्गोरिदम को यह निर्धारित करना होगा कि किस सर्वर को अनुरोधित बिंदु पर ले जाना है। एल्गोरिदम का लक्ष्य सभी सर्वरों द्वारा स्थानांतरित की जाने वाली कुल दूरी को छोटा रखना है, यह उस कुल दूरी के सापेक्ष है जिसे सर्वर एक इष्टतम प्रतिद्वंद्वी द्वारा स्थानांतरित कर सकते हैं जो अनुरोधों के पूरे अनुक्रम को पहले से जानता है।

इस समस्या को सबसे पहले [[मार्क मनश्शे]], लाइल ए. मैकगियोच और [[डेनियल स्लेटर]] (1988) ने सामने रखा था।<ref>{{Cite journal |last1=Manasse |first1=Mark |last2=McGeoch |first2=Lyle |last3=Sleator |first3=Daniel |date=1988-01-01 |title=ऑनलाइन समस्याओं के लिए प्रतिस्पर्धी एल्गोरिदम|url=https://doi.org/10.1145/62212.62243 |journal=Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing |series=STOC '88 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=322–333 |doi=10.1145/62212.62243 |isbn=978-0-89791-264-8|s2cid=13356897 }}</ref> के-सर्वर समस्या से संबंधित सबसे प्रमुख खुला प्रश्न तथाकथित के-सर्वर अनुमान है, जिसे मनसे एट अल द्वारा भी प्रस्तुत किया गया है। यह अनुमान बताता है कि एक मनमाना मीट्रिक स्थान में k-सर्वर समस्या को हल करने के लिए और किसी भी संख्या k सर्वर के लिए एक एल्गोरिदम है जिसका प्रतिस्पर्धी अनुपात बिल्कुल k है। मनस्से एट अल. जब k = 2 था, तब वे अपने अनुमान को साबित करने में सक्षम थे, और कुछ मीट्रिक स्थानों के लिए k के अधिक सामान्य मानों के लिए बिल्कुल k+1 अंक तक सीमित थे। [[ मार्क क्रोबक ]] और लॉरेंस एल. लारमोर (1991) ने वृक्ष मेट्रिक्स के अनुमान को साबित किया। मेट्रिक्स का विशेष मामला जिसमें सभी दूरियां समान होती हैं, पेजिंग समस्या कहलाती है क्योंकि यह मेमोरी कैश में पेज प्रतिस्थापन एल्गोरिदम की समस्या को मॉडल करती है, और यह पहले से ही ज्ञात था {{var|k}}-प्रतिस्पर्धी एल्गोरिदम (डैनियल स्लेटर और [[रॉबर्ट टार्जन]] 1985)। फिएट एट अल. (1990) ने पहली बार साबित किया कि किसी भी स्थिरांक k और किसी भी मीट्रिक स्थान के लिए परिमित प्रतिस्पर्धी अनुपात के साथ एक एल्गोरिदम मौजूद है, और अंत में कौट्सोपियास और [[क्रिस्टोस पापादिमित्रियोउ]] (1995) ने साबित किया कि वर्क फंक्शन एल्गोरिदम (डब्ल्यूएफए) में प्रतिस्पर्धी अनुपात 2k - 1 है। कई अन्य शोधकर्ताओं के प्रयासों ने प्रतिस्पर्धी अनुपात को कम कर दिया है {{var|k}} या एक बेहतर निचली सीमा प्रदान करना खुला रहता है {{As of|2014|lc=on}}. सबसे आम माना जाने वाला परिदृश्य यह है कि कार्य फ़ंक्शन एल्गोरिदम k-प्रतिस्पर्धी है। इस दिशा में, 2000 में बार्टल और कौट्सोपियास ने दिखाया कि यह कुछ विशेष मामलों के लिए सच है (यदि मीट्रिक स्थान एक रेखा, एक भारित तारा या k+2 बिंदुओं का कोई मीट्रिक है)।

2011 में, प्रतिस्पर्धी बाध्य Õ(लॉग) के साथ एक यादृच्छिक एल्गोरिदम<sup>2</sup>k लॉग<sup>3</sup>n) पाया गया.<ref>{{cite journal
 | last1 = Bansal | first1 = Nikhil
 | last2 = Buchbinder | first2 = Niv
 | last3 = Madry | first3 = Aleksander
 | last4 = Naor | first4 = Joseph | author4-link = Joseph Seffi Naor
 | doi = 10.1145/2783434
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 3424197
 | page = A40:1–A40:49
 | title = A polylogarithmic-competitive algorithm for the {{mvar|k}}-server problem
 | url = https://people.csail.mit.edu/madry/docs/kserver.pdf
 | volume = 62
 | year = 2015| arxiv = 1110.1580
 | s2cid = 15668961
 }}</ref><ref>{{Cite web|url=http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/|title = एक और कष्टप्रद खुली समस्या|date = 19 November 2011}}</ref> 2017 में, प्रतिस्पर्धी बाध्य ओ (लॉग) के साथ एक यादृच्छिक एल्गोरिदम<sup>6</sup>k) की घोषणा की गई,<ref>[https://arxiv.org/abs/1711.01789] which closely built on [https://arxiv.org/abs/1711.01085]</ref> लेकिन बाद में वापस ले लिया गया।<ref>{{Cite web|url=https://homes.cs.washington.edu/~jrl/papers/kserver-erratum.html|title=Erratum: Fusible HSTS and the randomized k-server conjecture}}</ref>
2022 में यह दिखाया गया कि अनुमान सामान्य तौर पर गलत है।<ref>{{Cite arXiv|title=यादृच्छिक के-सर्वर अनुमान गलत है|eprint=2211.05753 |last1=Bubeck |first1=Sébastien |last2=Coester |first2=Christian |last3=Rabani |first3=Yuval |year=2022 |class=cs.DS }}</ref>


== उदाहरण ==

समस्या को और अधिक ठोस बनाने के लिए, ग्राहकों को उनके उपकरण में समस्या होने पर ग्राहक सहायता तकनीशियनों को भेजने की कल्पना करें। हमारी उदाहरण समस्या में दो तकनीशियन हैं, मैरी और नूह, सैन फ्रांसिस्को, कैलिफ़ोर्निया में तीन ग्राहकों को सेवा दे रहे हैं; वाशिंगटन डीसी; और बाल्टीमोर, मैरीलैंड। के-सर्वर समस्या के रूप में, सर्वर तकनीशियन हैं, इसलिए के = 2 और यह 2-सर्वर समस्या है। वाशिंगटन और बाल्टीमोर हैं {{convert|35|mi|km}} अलग, जबकि सैन फ्रांसिस्को है {{convert|3000|mi|km}} दोनों से दूर, और शुरुआत में मैरी और नूह दोनों सैन फ्रांसिस्को में हैं।

अनुरोधों के लिए सर्वर निर्दिष्ट करने के लिए एक एल्गोरिदम पर विचार करें जो हमेशा अनुरोध के लिए निकटतम सर्वर निर्दिष्ट करता है, और मान लें कि प्रत्येक कार्यदिवस की सुबह वाशिंगटन में ग्राहक को सहायता की आवश्यकता होती है जबकि प्रत्येक कार्यदिवस दोपहर को बाल्टीमोर में ग्राहक को सहायता की आवश्यकता होती है, और सैन फ्रांसिस्को में ग्राहक को कभी भी सहायता की आवश्यकता नहीं होती है सहायता। फिर, हमारा एल्गोरिदम सर्वरों में से एक (जैसे मैरी) को वाशिंगटन क्षेत्र में नियुक्त करेगा, जिसके बाद वह हमेशा निकटतम सर्वर रहेगा और हमेशा सभी ग्राहक अनुरोधों के लिए उसे सौंपा जाएगा। इस प्रकार, हर दिन हमारा एल्गोरिदम वाशिंगटन और बाल्टीमोर के बीच और वापसी की यात्रा की लागत वहन करता है, {{convert|70|mi|km}}. इस अनुरोध पैटर्न के एक वर्ष के बाद, एल्गोरिथम खर्च हो जाएगा {{convert|20500|mi|km}} यात्रा: मैरी को पूर्वी तट पर भेजने के लिए 3,000, और वाशिंगटन और बाल्टीमोर के बीच यात्रा के लिए 17,500। दूसरी ओर, एक इष्टतम प्रतिद्वंद्वी जो भविष्य के अनुरोध कार्यक्रम को जानता है, वह मैरी और नूह दोनों को भुगतान करके क्रमशः वाशिंगटन और बाल्टीमोर भेज सकता था। {{convert|6000|mi|km}} एक बार यात्रा करें लेकिन फिर भविष्य की किसी भी यात्रा लागत से बचें। इस इनपुट पर हमारे एल्गोरिदम का प्रतिस्पर्धी अनुपात 20,500/6,000 या लगभग 3.4 है, और इस उदाहरण के मापदंडों को समायोजित करके इस एल्गोरिदम के प्रतिस्पर्धी अनुपात को मनमाने ढंग से बड़ा बनाया जा सकता है।

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

== संदर्भ ==
<references />

*{{cite journal
  |author1=[[Marek Chrobak|Chrobak, Marek]] |author2=[[Lawrence L. Larmore|Larmore, Lawrence L.]]
 | title = An optimal on-line algorithm for ''K''-servers on trees
  | journal = SIAM Journal on Computing
  | volume = 20
  | issue = 1
  | year = 1991
  | pages = 144–148
  | doi = 10.1137/0220008| citeseerx = 10.1.1.53.2395
  }}

*{{cite conference
  |author1=Fiat, A. |author2=Rabani, Y. |author3=Ravid, Y. | title = Competitive ''k''-server algorithms
  | book-title = Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science
  | date = 1990
  | pages = 454–463}}

*{{cite journal
  |author1=Koutsoupias, Elias |author2=[[Christos Papadimitriou|Papadimitriou, Christos H.]]
 | title = On the ''k''-server conjecture
  | journal = Journal of the ACM
  | volume = 42
  | issue = 5
  | year = 1995
  | pages = 971–983
  | doi = 10.1145/210118.210128|s2cid=5813837
 }}

*{{cite journal 
  |author1=Manasse, Mark |author2=McGeoch, Lyle A. |author3=[[Daniel Sleator|Sleator, Daniel D.]]
 | title=Competitive algorithms for server problems
  | journal= Journal of Algorithms
  | year=1990 
  | volume=11 
  | pages= 208–230
  | doi=10.1016/0196-6774(90)90003-W 
  | issue= 2}}

*{{cite journal
  |author1=[[Daniel Sleator|Sleator, Daniel D.]] |author2=[[Robert Tarjan|Tarjan, Robert E.]]
 | title = Amortized efficiency of list update and paging rules
  | journal = Communications of the ACM
  | volume = 28
  | year = 1985
  | pages = 202–208
  | doi = 10.1145/2786.2793
  | issue = 2|s2cid=2494305
 }}

[[Category: ऑनलाइन एल्गोरिदम]] [[Category: कंप्यूटर विज्ञान में अनसुलझी समस्याएं]] 



[[Category: Machine Translated Page]]
[[Category:Created On 08/07/2023]]