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

We give a deterministic, polynomial-time algorithm for approximately countingthe number of {0,1}-solutions to any instance of the knapsack problem. On aninstance of length n with total weight W and accuracy parameter eps, ouralgorithm produces a (1 + eps)-multiplicative approximation in time poly(n,logW,1/eps). We also give algorithms with identical guarantees for general integerknapsack, the multidimensional knapsack problem (with a constant number ofconstraints) and for contingency tables (with a constant number of rows).Previously, only randomized approximation schemes were known for these problemsdue to work by Morris and Sinclair and work by Dyer.  Our algorithms work by constructing small-width, read-once branching programsfor approximating the underlying solution space under a carefully chosendistribution. As a byproduct of this approach, we obtain new query algorithmsfor learning functions of k halfspaces with respect to the uniform distributionon {0,1}^n. The running time of our algorithm is polynomial in the accuracyparameter eps. Previously even for the case of k=2, only algorithms with anexponential dependence on eps were known.

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs