English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In the dynamic linear program (LP) problem, we are given an LP undergoingupdates and we need to maintain an approximately optimal solution. Recently,significant attention (e.g., [Gupta et al. STOC'17; Arar et al. ICALP'18, WajcSTOC'20]) has been devoted to the study of special cases of dynamic packing andcovering LPs, such as the dynamic fractional matching and set cover problems.But until now, there is no non-trivial dynamic algorithm for general packingand 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 partiallydynamic setting (where updates can either only relax or only restrict thefeasible region), we give near-optimal deterministic $\epsilon$-approximationalgorithms with polylogarithmic amortized update time. Then, we show that bothpartially dynamic updates and amortized update time are necessary; without anyof these conditions, the trivial algorithm that recomputes the solution fromscratch after every update is essentially the best possible, assuming SETH.  To obtain our results, we initiate a systematic study of the multiplicativeweights update (MWU) method in the dynamic setting. As by-products of ourtechniques, we also obtain the first online $(1+\epsilon)$-competitivealgorithms for both covering and packing LPs with polylogarithmic recourse, andthe first streaming algorithms for covering and packing LPs with linear spaceand polylogarithmic passes.

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates