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

The Subset Sum problem asks whether a given set of $n$ positive integerscontains a subset of elements that sum up to a given target $t$. It is anoutstanding open question whether the $O^*(2^{n/2})$-time algorithm for SubsetSum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case settingby a "truly faster", $O^*(2^{(0.5-\delta)n})$-time algorithm, with someconstant $\delta > 0$. Continuing an earlier work [STACS 2015], we study SubsetSum parameterized by the maximum bin size $\beta$, defined as the largestnumber of subsets of the $n$ input integers that yield the same sum. For every$\epsilon > 0$ we give a truly faster algorithm for instances with $\beta \leq2^{(0.5-\epsilon)n}$, as well as instances with $\beta \geq 2^{0.661n}$.Consequently, we also obtain a characterization in terms of the popular densityparameter $n/\log_2 t$: if all instances of density at least $1.003$ admit atruly faster algorithm, then so does every instance. This goes against thecurrent intuition that instances of density 1 are the hardest, and therefore isa step toward answering the open question in the affirmative. Our results stemfrom novel combinations of earlier algorithms for Subset Sum and a study of anextremal question in additive combinatorics connected to the problem ofUniquely Decodable Code Pairs in information theory.

Dense Subset Sum may be the hardest