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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Subset sum is a very old and fundamental problem in theoretical computerscience. In this problem, $n$ items with weights $w_1, w_2, w_3, \ldots, w_n$are given as input and the goal is to find out if there is a subset of themwhose weights sum up to a given value $t$. While the problem is NP-hard ingeneral, when the values are non-negative integer, subset sum can be solved inpseudo-polynomial time $~\widetilde O(n+t)$.  In this work, we consider the dynamic variant of subset sum. In this setting,an upper bound $\tmax$ is provided in advance to the algorithm and in eachoperation, either a new item is added to the problem or for a given integervalue $t \leq \tmax$, the algorithm is required to output whether there is asubset of items whose sum of weights is equal to $t$. Unfortunately, none ofthe existing subset sum algorithms is able to process these operations in trulysublinear time\footnote{Truly sublinear means $n^{1-\Omega(1)}$.} in terms of$\tmax$.  Our main contribution is an algorithm whose amortized processingtime\footnote{Since the runtimes are amortized, we do not use separate termsupdate time and query time for different operations and use processing time forall types of operations.} for each operation is truly sublinear in $\tmax$ whenthe number of operations is at least $\tmax^{2/3+\Omega(1)}$. We also show thatwhen both element addition and element removal are allowed, there is noalgorithm that can process each operation in time $\tmax^{1-\Omega(1)}$ onaverage unless \textsf{SETH}\footnote{The \textit{strong exponential timehypothesis} states that no algorithm can solve the satisfiability problem intime $2^{n(1-\Omega(1))}$.} fails.

Dynamic Subset Sum with Truly Sublinear Processing Time