Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates

Explore a comprehensive lecture on dynamic algorithms for packing-covering linear programs using multiplicative weight updates. Delve into the complexity of dynamic packing and covering LPs, examining near-optimal deterministic ε-approximation algorithms with polylogarithmic amortized update time in partially dynamic settings. Investigate the necessity of partially dynamic updates and amortized update time, and learn how the trivial algorithm becomes the best possible solution without these conditions, assuming SETH. Gain insights into the systematic study of the multiplicative weights update (MWU) method in dynamic settings, and understand its applications to dynamic fractional matching and set cover problems. Presented by Sayan Bhattacharya from the University of Warwick, this 47-minute talk is part of the Dynamic Graphs and Algorithm Design series at the Simons Institute.