Selective algorithm processing of subset sum distributions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913503947784192 |
|---|---|
| author | Dawes, Nick |
| author_facet | Dawes, Nick |
| contents | The efficiency of exact subset sum problem algorithms which compute individual subset sums is defined as $e=min(T/z, 1)$, where $z$ is the number of subset sums computed. $e$ is related to these algorithms' computational complexity. This system maps the sums into $kn$ bins to select its most efficient algorithm for each bin for each input value. These algorithms include additive, subtractive and repeated value dynamic programming. Cases which would otherwise be processed inefficiently (eg: all even values) are handled by modular arithmetic and by dynamically partioning the input values. The system's experimentally validated efficiency corresponds to O(max($T$, $n^2$)) with space complexity O(max($T$, $n$)), for $k=2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11076 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Selective algorithm processing of subset sum distributions Dawes, Nick Data Structures and Algorithms F.2.1 The efficiency of exact subset sum problem algorithms which compute individual subset sums is defined as $e=min(T/z, 1)$, where $z$ is the number of subset sums computed. $e$ is related to these algorithms' computational complexity. This system maps the sums into $kn$ bins to select its most efficient algorithm for each bin for each input value. These algorithms include additive, subtractive and repeated value dynamic programming. Cases which would otherwise be processed inefficiently (eg: all even values) are handled by modular arithmetic and by dynamically partioning the input values. The system's experimentally validated efficiency corresponds to O(max($T$, $n^2$)) with space complexity O(max($T$, $n$)), for $k=2$. |
| title | Selective algorithm processing of subset sum distributions |
| topic | Data Structures and Algorithms F.2.1 |
| url | https://arxiv.org/abs/2409.11076 |