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. In this paper, 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 $\epsilon$-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. As by-products of our techniques, we also obtain the first online $(1+\epsilon)$-competitive algorithms for both covering and packing LPs with polylogarithmic recourse, and the first streaming algorithms for covering and packing LPs with linear space and polylogarithmic passes.
翻译:在动态线性程序( LP) 问题中, 我们得到了一个正在更新的 LP, 我们需要保持一个大致最佳的解决方案。 最近, 大量关注( 例如, [Gupta 等STOC' 17; Arar 等等CricalP'18, Wajc STOC' 20] ) 用于研究动态包装的特殊案例, 覆盖 LP, 比如动态分数匹配和设置覆盖问题。 但直到现在, 普通包装和覆盖 LP 还没有非三维的动态算法。 在本文件中, 我们解决动态包装和覆盖 LPs 的复杂程度, 在更新时, 我们解决了动态包装和覆盖 LPs, 在部分动态设置( 更新只能放松或限制可行区域) 的情况下, 我们给出了几乎最佳的 确定性 $\ epsiol$- approcolmomation 算法 。 然后, 我们用部分的动态流更新和重新配置时间来显示我们所需要的; 在任何这些条件中, 小数级的算算法中, 将每个系统化的方法都进行一次重新设定。