Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
summary
Maintains fractional solutions to general packing and covering LPs under partially dynamic updates and proves both upper and conditional lower bounds: a near-optimal deterministic ε-approximation with polylogarithmic amortized update time using a dynamized multiplicative-weights-update (MWU) scheme, T ≈ λ log n / ε^2 rounds in the static view, phase-based batching to get near-linear preprocessing, and a lemma that each constraint is “enforced” only polylog many times; shows fully‑dynamic or worst‑case bounds are ruled out by SETH-style reductions.
AI-written summary · about