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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the incremental knapsack problem ($\IK$), we are given a knapsack whosecapacity grows weakly as a function of time. There is a time horizon of $T$periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1,\ldots, T$. We are also given a set $S$ of $N$ items to be placed in theknapsack. Item $i$ has a value of $v_i$ and a weight of $w_i$ that isindependent of the time period. At any time period $t$, the sum of the weightsof the items in the knapsack cannot exceed the knapsack capacity $B_t$.Moreover, once an item is placed in the knapsack, it cannot be removed from theknapsack at a later time period. We seek to maximize the sum of (discounted)knapsack values over time subject to the capacity constraints. We first give aconstant factor approximation algorithm for $\IK$, under mild restrictions onthe growth rate of $B_t$ (the constant factor depends on the growth rate). Wethen give a PTAS for $\IIK$, the special case of $\IK$ with no discounting,when $T = O(\sqrt{\log N})$.

Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming