{"ID":2825504,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.21195","arxiv_id":"2512.21195","title":"An O(nlogn) approximate knapsack algorithm","abstract":"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.","short_abstract":"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 fr...","url_abs":"https://arxiv.org/abs/2512.21195","url_pdf":"https://arxiv.org/pdf/2512.21195v2","authors":"[\"Nick Dawes\"]","published":"2025-12-24T14:18:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}