The k-Server Problem with Advice in d Dimensions and on the Sphere
| العنوان: | The k-Server Problem with Advice in d Dimensions and on the Sphere |
|---|---|
| المؤلفون: | Dennis Komm, Elisabet Burjons, Marcel Schöngens |
| المصدر: | SOFSEM 2018: Theory and Practice of Computer Science ISBN: 9783319731162 SOFSEM |
| بيانات النشر: | Springer International Publishing, 2017. |
| سنة النشر: | 2017 |
| مصطلحات موضوعية: | Discrete mathematics, Euclidean space, Computer science, K-server problem, 0102 computer and information sciences, 02 engineering and technology, Curvature, 01 natural sciences, Metric space, 010201 computation theory & mathematics, Metric (mathematics), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Online algorithm, Constant (mathematics), Advice (complexity) |
| الوصف: | We study the impact of additional information on the hardness of the k-server problem on different metric spaces. To this end, we consider the well-known model of computing with advice. In particular, we design an algorithm for the d-dimensional Euclidean space, which generalizes a known result for the Euclidean plane. As another relevant setting, we investigate a metric space with positive curvature; in particular, the sphere. Both algorithms have constant strict competitive ratios while reading a constant number of advice bits with every request, independent of the number k of servers, and solely depending on parameters of the underlying metric structure. |
| ردمك: | 978-3-319-73116-2 |
| DOI: | 10.1007/978-3-319-73117-9_28 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::bd75e0930bb9025994e4767816fceee2 https://doi.org/10.1007/978-3-319-73117-9_28 |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........bd75e0930bb9025994e4767816fceee2 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783319731162 |
|---|---|
| DOI: | 10.1007/978-3-319-73117-9_28 |