### Samenvatting

The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a ktuple r = (r1; r2; : : : ; rk) and to serve it, we need to move some server si to the point ri ϵ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > ϵ servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k > 2k and O(k3 log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k -1. We also give a 22O(k) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

Originele taal-2 | Engels |
---|---|

Titel | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |

Redacteuren | Artur Czumaj |

Plaats van productie | s.l. |

Uitgeverij | Society for Industrial and Applied Mathematics (SIAM) |

Pagina's | 992-1001 |

Aantal pagina's | 10 |

ISBN van elektronische versie | 978-1-61197-503-1 |

DOI's | |

Status | Gepubliceerd - 2018 |

Evenement | 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, Verenigde Staten van Amerika Duur: 7 jan 2018 → 10 jan 2018 Congresnummer: 29 https://www.siam.org/meetings/da18/ |

### Congres

Congres | 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) |
---|---|

Verkorte titel | SODA 2018 |

Land | Verenigde Staten van Amerika |

Stad | New Orleans |

Periode | 7/01/18 → 10/01/18 |

Internet adres |

## Vingerafdruk Duik in de onderzoeksthema's van 'Competitive algorithms for generalized k-server in uniform metrics.'. Samen vormen ze een unieke vingerafdruk.

## Citeer dit

*29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*(blz. 992-1001). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975031.64