Dynamic Algorithms for ๐‘˜-center on Graphs

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=aOjkVGFnlaU


Duration: 50:44
247 views
9

Sebastian Forster (University of Salzburg)
https://simons.berkeley.edu/talks/sebastian-forster-university-salzburg-2023-09-19
Dynamic Graphs and Algorithm Design

We present the first efficient approximation algorithms for the ๐‘˜-center problem on dynamic graphs undergoing edge updates. Joint work with Emilio Cruciani, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos.



Other Videos By Simons Institute for the Theory of Computing


2023-09-21On Dynamic Graph Approximations: The case of j-Trees
2023-09-21On Engineering Dynamic Graph Algorithms
2023-09-21Dynamic Graphs on the GPU
2023-09-20Dynamic PageRank: Additive Error and Batch Recomputation
2023-09-20Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
2023-09-20Online List Labeling: Breaking the log^2 n Barrier
2023-09-20Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models
2023-09-20Decremental Shortest Paths against an Adaptive Adversary
2023-09-19Dynamic Matching: Rounding & Sparsification (And New Tools)
2023-09-19Parallel Batch-Dynamic Graph Representations
2023-09-19Dynamic Algorithms for ๐‘˜-center on Graphs
2023-09-19A Blackbox Reduction for Adaptive Adversaries using Differential Privacy
2023-09-19Recent Progress on Sublinear Time Algorithms for Maximum Matching: Upper Bounds
2023-09-18Parallelism in Dynamic Graph Algorithms
2023-09-18Optimizing Dynamic-Graph Data Structures on Multicores with the Locality-First Strategy
2023-09-18Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
2023-09-18Approximating Edit Distance in the Fully Dynamic Model
2023-09-18Lightning Talks
2023-09-12Dynamic Graph Algorithms: What We Know and What We Donโ€™t | Richard M. Karp Distinguished Lecture
2023-09-08Probabilistic and Logical Circuits for Tractable Causal Reasoning
2023-09-08Probabilistic Reasoning and Learning for Trustworthy AI


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Dynamic Graphs and Algorithm Design
Sebastian Forster