## Abstract

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem. While in many applications the input may naturally be modeled as a graph, all prior works on k-center problem in dynamic settings are on point sets in arbitrary metric spaces. In this paper, we give a deterministic decremental (2 + ϵ)-approximation algorithm and a randomized incremental (4 + ϵ)-approximation algorithm, both with amortized update time kn^{o(1)} for weighted graphs. Moreover, we show a reduction that leads to a fully dynamic (2 + ϵ)-approximation algorithm for the k-center problem, with worst-case update time that is within a factor k of the state-of-the-art upper bound for maintaining (1+ϵ)-approximate single-source distances in graphs. Matching this bound is a natural goalpost because the approximate distances of each vertex to its center can be used to maintain a (2+ϵ)-approximation of the graph diameter and the fastest known algorithms for such a diameter approximation also rely on maintaining approximate single-source distances.

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

Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Editors | David P. Woodruff |

Publisher | SIAM |

Pages | 3441-3462 |

Number of pages | 22 |

ISBN (Electronic) | 9781611977912 |

DOIs | |

Publication status | Published - 2024 |

Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |

### Publication series

Name | Proceedings series |
---|---|

Publisher | SIAM |

### Conference

Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 7/01/24 → 10/01/24 |

### Bibliographical note

Publisher Copyright:Copyright © 2024 by SIAM.