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 development of a satisfying and rigorous mathematical understanding ofthe performance of neural networks is a major challenge in artificialintelligence. Against this background, we study the expressive power of neuralnetworks through the example of the classical NP-hard Knapsack Problem. Ourmain contribution is a class of recurrent neural networks (RNNs) with rectifiedlinear units that are iteratively applied to each item of a Knapsack instanceand thereby compute optimal or provably good solution values. We show that anRNN of depth four and width depending quadratically on the profit of an optimumKnapsack solution is sufficient to find optimum Knapsack solutions. We alsoprove the following tradeoff between the size of an RNN and the quality of thecomputed Knapsack solution: for Knapsack instances consisting of $n$ items, anRNN of depth five and width $w$ computes a solution of value at least$1-\mathcal{O}(n^2/\sqrt{w})$ times the optimum solution value. Our resultsbuild upon a classical dynamic programming formulation of the Knapsack Problemas well as a careful rounding of profit values that are also at the core of thewell-known fully polynomial-time approximation scheme for the Knapsack Problem.A carefully conducted computational study qualitatively supports ourtheoretical size bounds. Finally, we point out that our results can begeneralized to many other combinatorial optimization problems that admitdynamic programming solution methods, such as various Shortest Path Problems,the Longest Common Subsequence Problem, and the Traveling Salesperson Problem.

Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size