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

Consider positive integral solutions $x \in \mathbb{Z}^{n+1}$ to the equation$a_0 x_0 + \ldots + a_n x_n = t$. In the so called unbounded subset sumproblem, the objective is to decide whether such a solution exists, whereas inthe Frobenius problem, the objective is to compute the largest $t$ such thatthere is no such solution.  In this paper we study the algorithmic complexity of the unbounded subsetsum, the Frobenius problem and a generalization of the problems. Moreprecisely, we study pseudo-polynomial time algorithms with a running time thatdepends on the smallest number $a_0$ or respectively the largest number $a_n$.For the parameter $a_0$, we show that all considered problems aresubquadratically equivalent to $(min,+)$-convolution, a fundamental algorithmicproblem from the area of fine-grained complexity. By this equivalence, weobtain hardness results for the considered problems (based on the assumptionthat an algorithm with a subquadratic running time for $(min,+)$-convolutiondoes not exist) as well as algorithms with improved running time. The proof forthe equivalence makes use of structural properties of solutions, a techniquethat was developed in the area of integer programming.  In case of the complexity of the problems parameterized by $a_n$, we presentimproved algorithms. For example we give a quasi linear time algorithm for theFrobenius problem as well as a hardness result based on the strong exponentialtime hypothesis.

On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem