Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

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


Category:
Vlog
Duration: 46:58
258 views
6

Sayan Bhattacharya (University of Warwick)
https://simons.berkeley.edu/talks/sayan-bhattacharya-university-warwick-2023-09-20
Dynamic Graphs and Algorithm Design

In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention has been devoted to the study of special cases of dynamic packing and covering LPs, such as the dynamic fractional matching and set cover problems. But prior to our work, there was no non-trivial dynamic algorithm for general packing and covering LPs.

We settle the complexity of dynamic packing and covering LPs, up to a polylogarithmic factor in update time. More precisely, in the partially dynamic setting (where updates can either only relax or only restrict the feasible region), we give near-optimal deterministic ϵ-approximation algorithms with polylogarithmic amortized update time. Then, we show that both partially dynamic updates and amortized update time are necessary; without any of these conditions, the trivial algorithm that recomputes the solution from scratch after every update is essentially the best possible, assuming SETH.

To obtain our results, we initiate a systematic study of the multiplicative weights update (MWU) method in the dynamic setting.

Joint work with Peter Kiss and Thatchaphol Saranurak.



Other Videos By Simons Institute for the Theory of Computing


2023-09-25Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
2023-09-22Accelerating the Multiplicative-Weights Framework for Graph Linear Programs
2023-09-22Parallel Batch-Dynamic Graph Algorithms
2023-09-22Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds
2023-09-21Faster High Accuracy Multi-Commodity Flows via Graph Techniques
2023-09-21Minimum Isolating Cuts: A New Tool for Solving Minimum Cut Problems
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


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