Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
Sayan Bhattacharya, Péter Kiss, Thatchaphol Saranurak · Society for Industrial and Applied Mathematics eBooks · 2023
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 (e.g. [Gupta et al. STOC'17; Arar et al. ICALP'18, Wajc STOC'20]) 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 until now, there is no non-trivial dynamic algorithm for general packing and covering LPs.