The infinite server problem
We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this proble...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Conference item |
| Vydáno: |
Schloss Dagstuhl
2017
|
| _version_ | 1826265828449845248 |
|---|---|
| author | Coester, C Koutsoupias, E Lazos, F |
| author_facet | Coester, C Koutsoupias, E Lazos, F |
| author_sort | Coester, C |
| collection | OXFORD |
| description | We study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which implies the same lower bound for the (h,k)-server problem even when k>>h and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case. |
| first_indexed | 2024-03-06T20:29:44Z |
| format | Conference item |
| id | oxford-uuid:30a53614-cf5a-4e94-a468-d02c6634e3c6 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:29:44Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:30a53614-cf5a-4e94-a468-d02c6634e3c62022-03-26T13:02:43ZThe infinite server problemConference itemhttp://purl.org/coar/resource_type/c_5794uuid:30a53614-cf5a-4e94-a468-d02c6634e3c6Symplectic Elements at OxfordSchloss Dagstuhl2017Coester, CKoutsoupias, ELazos, FWe study a variant of the k-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the (h,k)-server problem, in which an online algorithm with k servers competes against an offline algorithm with h servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the (h,k)-server problem has bounded competitive ratio for some k=O(h). We give a lower bound of 3.146 for the competitive ratio of the infinite server problem, which implies the same lower bound for the (h,k)-server problem even when k>>h and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case. |
| spellingShingle | Coester, C Koutsoupias, E Lazos, F The infinite server problem |
| title | The infinite server problem |
| title_full | The infinite server problem |
| title_fullStr | The infinite server problem |
| title_full_unstemmed | The infinite server problem |
| title_short | The infinite server problem |
| title_sort | infinite server problem |
| work_keys_str_mv | AT coesterc theinfiniteserverproblem AT koutsoupiase theinfiniteserverproblem AT lazosf theinfiniteserverproblem AT coesterc infiniteserverproblem AT koutsoupiase infiniteserverproblem AT lazosf infiniteserverproblem |