### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana |

Place of Publication | s.l. |

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

Pages | 992-1001 |

ISBN (Electronic) | 978-1-61197-503-1 |

DOIs | |

Publication status | Published - 2018 |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, United States Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29 https://www.siam.org/meetings/da18/ |

### Conference

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

Abbreviated title | SODA 2018 |

Country | United States |

City | New Orleans |

Period | 7/01/18 → 10/01/18 |

Internet address |

### Fingerprint

### Cite this

*Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana*(pp. 992-1001). s.l.: Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975031.64

}

*Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana.*Society for Industrial and Applied Mathematics (SIAM), s.l., pp. 992-1001, 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, United States, 7/01/18. https://doi.org/10.1137/1.9781611975031.64

**Competitive algorithms for generalized k-server in uniform metrics.** / Bansal, N.; Elias, M.; Koumoutsos, G.; Nederlof, J.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Competitive algorithms for generalized k-server in uniform metrics.

AU - Bansal, N.

AU - Elias, M.

AU - Koumoutsos, G.

AU - Nederlof, J.

PY - 2018

Y1 - 2018

N2 - 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 k-tuple 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 > 2 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.

AB - 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 k-tuple 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 > 2 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.

U2 - 10.1137/1.9781611975031.64

DO - 10.1137/1.9781611975031.64

M3 - Conference contribution

SP - 992

EP - 1001

BT - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 7-10 January 2018, New Orleans, Louisiana

PB - Society for Industrial and Applied Mathematics (SIAM)

CY - s.l.

ER -