Dynamic Algorithms for 𝑘-center on Graphs

on YouTube ↗51m

" summary

Presents the first algorithms that maintain k-center on an evolving undirected graph by reducing to dynamic (1+ε)-SSSP: a fully dynamic 2+ε approximation with update time roughly k·n^1.529 (unweighted), k·n^1.823 (weighted) using adaptive-adversary SSSP routines that rely on fast matrix multiplication; decremental algorithms keep an O(k) overhead (near k·n^{o(1)} per update) by restarting SSSP from a super-source, while the incremental algorithm gives a 4+ε approximation via random sampling, dominating sets and bounded recourse; getting 2+ε incrementally remains open.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 1:46Dynamic Graph Clustering
3. 4:15Metric Spaces and Graphs
4. 5:13Dynamic Model
5. 7:56Related Work
6. 18:10Reminder: Gonzalez's Algorithm
7. 18:59Reduction to SSSP: Simulating Gonzalez's Algorithm
8. 26:19Decremental Algorithm
9. 28:38Example and Running Time
10. 32:02Incremental Algorithm
11. 38:42Dominating Sets via Random Sampling
12. 40:26An Open Problem