An O(nlogn) approximate knapsack algorithm
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911340434554880 |
|---|---|
| author | Dawes, Nick |
| author_facet | Dawes, Nick |
| contents | A modified dynamic programming algorithm rapidly and accurately solves large 0/1 knapsack problems. It has computational O(nlogn), space O(nlogn) and predictable maximum error. Experimentally it's accuracy increases faster than linearly with the solution size k. Problems with k=1e3 are solved with an average maximum fractional error of 1e-4 and problems with k=1e5 with an average maximum fractional error of 1e-7. The algorithm runs in constant time for all problems with a given n. On a common desktop computer the algorithm processes n=1e3 problems in 1e-3 seconds and n=1e6 problems in 2 seconds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21195 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An O(nlogn) approximate knapsack algorithm Dawes, Nick Data Structures and Algorithms F.2.1 A modified dynamic programming algorithm rapidly and accurately solves large 0/1 knapsack problems. It has computational O(nlogn), space O(nlogn) and predictable maximum error. Experimentally it's accuracy increases faster than linearly with the solution size k. Problems with k=1e3 are solved with an average maximum fractional error of 1e-4 and problems with k=1e5 with an average maximum fractional error of 1e-7. The algorithm runs in constant time for all problems with a given n. On a common desktop computer the algorithm processes n=1e3 problems in 1e-3 seconds and n=1e6 problems in 2 seconds. |
| title | An O(nlogn) approximate knapsack algorithm |
| topic | Data Structures and Algorithms F.2.1 |
| url | https://arxiv.org/abs/2512.21195 |