A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients Article Swipe
Benchmark instances for the unbounded knapsack problem are typically generated according to specific criteria within a given constant range $R$, and these instances can be referred to as the unbounded knapsack problem with bounded coefficients (UKPB). In order to increase the difficulty of solving these instances, the knapsack capacity $C$ is usually set to a very large value. Therefore, an exact algorithm that neither time complexity nor space complexity includes the capacity coefficient $C$ is highly anticipated. In this paper, we propose an exact algorithm with time complexity of $O(R^4)$ and space complexity of $O(R^3)$. The algorithm initially divides the multiset $N$ into two multisubsets, $N_1$ and $N_2$, based on the profit density of their types. For the multisubset $N_2$ composed of types with profit density lower than the maximum profit density type, we utilize a recent branch and bound (B\&B) result by Dey et al. (Math. Prog., pp 569-587, 2023) to determine the maximum selection number for types in $N_2$. We then employ the Unbounded-DP algorithm to exactly solve for the types in $N_2$. For the multisubset $N_1$ composed of the maximum profit density type and its counterparts with the same profit density, we transform it into a linear Diophantine equation and leverage relevant conclusions from the Frobenius problem to solve it efficiently. In particular, the proof techniques required by the algorithm are primarily covered in the first-year mathematics curriculum, which is convenient for subsequent researchers to grasp.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2403.11320
- https://arxiv.org/pdf/2403.11320
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4392972197
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4392972197Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2403.11320Digital Object Identifier
- Title
-
A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficientsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-03-17Full publication date if available
- Authors
-
Yang YangList of authors in order
- Landing page
-
https://arxiv.org/abs/2403.11320Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2403.11320Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2403.11320Direct OA link when available
- Concepts
-
Knapsack problem, Constant (computer programming), Bounded function, Polynomial-time approximation scheme, Time complexity, Continuous knapsack problem, Mathematics, Computer science, Algorithm, Mathematical optimization, Mathematical analysis, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4392972197 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2403.11320 |
| ids.doi | https://doi.org/10.48550/arxiv.2403.11320 |
| ids.openalex | https://openalex.org/W4392972197 |
| fwci | |
| type | preprint |
| title | A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12176 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9987999796867371 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2209 |
| topics[0].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[0].display_name | Optimization and Packing Problems |
| topics[1].id | https://openalex.org/T11814 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9965999722480774 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2209 |
| topics[1].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[1].display_name | Advanced Manufacturing and Logistics Optimization |
| topics[2].id | https://openalex.org/T12288 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9817000031471252 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Optimization and Search Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C113138325 |
| concepts[0].level | 2 |
| concepts[0].score | 0.8817448616027832 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q864457 |
| concepts[0].display_name | Knapsack problem |
| concepts[1].id | https://openalex.org/C2777027219 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7627801895141602 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1284190 |
| concepts[1].display_name | Constant (computer programming) |
| concepts[2].id | https://openalex.org/C34388435 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6961354613304138 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[2].display_name | Bounded function |
| concepts[3].id | https://openalex.org/C99140742 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5099831819534302 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q843550 |
| concepts[3].display_name | Polynomial-time approximation scheme |
| concepts[4].id | https://openalex.org/C311688 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5082104206085205 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[4].display_name | Time complexity |
| concepts[5].id | https://openalex.org/C94569963 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5047246217727661 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q5165487 |
| concepts[5].display_name | Continuous knapsack problem |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.49752572178840637 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C41008148 |
| concepts[7].level | 0 |
| concepts[7].score | 0.41757577657699585 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[7].display_name | Computer science |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.41744381189346313 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C126255220 |
| concepts[9].level | 1 |
| concepts[9].score | 0.37088513374328613 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[9].display_name | Mathematical optimization |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.1344488263130188 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| concepts[11].id | https://openalex.org/C199360897 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[11].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/knapsack-problem |
| keywords[0].score | 0.8817448616027832 |
| keywords[0].display_name | Knapsack problem |
| keywords[1].id | https://openalex.org/keywords/constant |
| keywords[1].score | 0.7627801895141602 |
| keywords[1].display_name | Constant (computer programming) |
| keywords[2].id | https://openalex.org/keywords/bounded-function |
| keywords[2].score | 0.6961354613304138 |
| keywords[2].display_name | Bounded function |
| keywords[3].id | https://openalex.org/keywords/polynomial-time-approximation-scheme |
| keywords[3].score | 0.5099831819534302 |
| keywords[3].display_name | Polynomial-time approximation scheme |
| keywords[4].id | https://openalex.org/keywords/time-complexity |
| keywords[4].score | 0.5082104206085205 |
| keywords[4].display_name | Time complexity |
| keywords[5].id | https://openalex.org/keywords/continuous-knapsack-problem |
| keywords[5].score | 0.5047246217727661 |
| keywords[5].display_name | Continuous knapsack problem |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.49752572178840637 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/computer-science |
| keywords[7].score | 0.41757577657699585 |
| keywords[7].display_name | Computer science |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.41744381189346313 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[9].score | 0.37088513374328613 |
| keywords[9].display_name | Mathematical optimization |
| keywords[10].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[10].score | 0.1344488263130188 |
| keywords[10].display_name | Mathematical analysis |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2403.11320 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2403.11320 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2403.11320 |
| locations[1].id | doi:10.48550/arxiv.2403.11320 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2403.11320 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5100397725 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-0608-9408 |
| authorships[0].author.display_name | Yang Yang |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Yang, Yang |
| authorships[0].is_corresponding | True |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2403.11320 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-03-20T00:00:00 |
| display_name | A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12176 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9987999796867371 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2209 |
| primary_topic.subfield.display_name | Industrial and Manufacturing Engineering |
| primary_topic.display_name | Optimization and Packing Problems |
| related_works | https://openalex.org/W4288642040, https://openalex.org/W2908214350, https://openalex.org/W3169691842, https://openalex.org/W3166857172, https://openalex.org/W1701984136, https://openalex.org/W2122137596, https://openalex.org/W2060645964, https://openalex.org/W1984121220, https://openalex.org/W1601835603, https://openalex.org/W1556368910 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2403.11320 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2403.11320 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2403.11320 |
| primary_location.id | pmh:oai:arXiv.org:2403.11320 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2403.11320 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2403.11320 |
| publication_date | 2024-03-17 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 15, 54, 135, 198 |
| abstract_inverted_index.In | 36, 77, 214 |
| abstract_inverted_index.We | 161 |
| abstract_inverted_index.an | 59, 82 |
| abstract_inverted_index.as | 27 |
| abstract_inverted_index.be | 24 |
| abstract_inverted_index.by | 142, 220 |
| abstract_inverted_index.et | 144 |
| abstract_inverted_index.in | 159, 173, 226 |
| abstract_inverted_index.is | 50, 74, 232 |
| abstract_inverted_index.it | 196, 212 |
| abstract_inverted_index.of | 42, 88, 93, 113, 121, 180 |
| abstract_inverted_index.on | 109 |
| abstract_inverted_index.pp | 148 |
| abstract_inverted_index.to | 11, 26, 38, 53, 151, 167, 210, 237 |
| abstract_inverted_index.we | 80, 133, 194 |
| abstract_inverted_index.$C$ | 49, 73 |
| abstract_inverted_index.$N$ | 101 |
| abstract_inverted_index.Dey | 143 |
| abstract_inverted_index.For | 116, 175 |
| abstract_inverted_index.The | 95 |
| abstract_inverted_index.al. | 145 |
| abstract_inverted_index.and | 20, 90, 106, 138, 186, 202 |
| abstract_inverted_index.are | 7, 223 |
| abstract_inverted_index.can | 23 |
| abstract_inverted_index.for | 2, 157, 170, 234 |
| abstract_inverted_index.its | 187 |
| abstract_inverted_index.nor | 66 |
| abstract_inverted_index.set | 52 |
| abstract_inverted_index.the | 3, 28, 40, 46, 70, 99, 110, 117, 128, 153, 164, 171, 176, 181, 190, 207, 216, 221, 227 |
| abstract_inverted_index.two | 103 |
| abstract_inverted_index.$R$, | 19 |
| abstract_inverted_index.from | 206 |
| abstract_inverted_index.into | 102, 197 |
| abstract_inverted_index.same | 191 |
| abstract_inverted_index.than | 127 |
| abstract_inverted_index.that | 62 |
| abstract_inverted_index.then | 162 |
| abstract_inverted_index.this | 78 |
| abstract_inverted_index.time | 64, 86 |
| abstract_inverted_index.type | 185 |
| abstract_inverted_index.very | 55 |
| abstract_inverted_index.with | 32, 85, 123, 189 |
| abstract_inverted_index.$N_1$ | 105, 178 |
| abstract_inverted_index.$N_2$ | 119 |
| abstract_inverted_index.2023) | 150 |
| abstract_inverted_index.based | 108 |
| abstract_inverted_index.bound | 139 |
| abstract_inverted_index.exact | 60, 83 |
| abstract_inverted_index.given | 16 |
| abstract_inverted_index.large | 56 |
| abstract_inverted_index.lower | 126 |
| abstract_inverted_index.order | 37 |
| abstract_inverted_index.proof | 217 |
| abstract_inverted_index.range | 18 |
| abstract_inverted_index.solve | 169, 211 |
| abstract_inverted_index.space | 67, 91 |
| abstract_inverted_index.their | 114 |
| abstract_inverted_index.these | 21, 44 |
| abstract_inverted_index.type, | 132 |
| abstract_inverted_index.types | 122, 158, 172 |
| abstract_inverted_index.which | 231 |
| abstract_inverted_index.$N_2$, | 107 |
| abstract_inverted_index.$N_2$. | 160, 174 |
| abstract_inverted_index.(Math. | 146 |
| abstract_inverted_index.Prog., | 147 |
| abstract_inverted_index.branch | 137 |
| abstract_inverted_index.employ | 163 |
| abstract_inverted_index.grasp. | 238 |
| abstract_inverted_index.highly | 75 |
| abstract_inverted_index.linear | 199 |
| abstract_inverted_index.number | 156 |
| abstract_inverted_index.paper, | 79 |
| abstract_inverted_index.profit | 111, 124, 130, 183, 192 |
| abstract_inverted_index.recent | 136 |
| abstract_inverted_index.result | 141 |
| abstract_inverted_index.types. | 115 |
| abstract_inverted_index.value. | 57 |
| abstract_inverted_index.within | 14 |
| abstract_inverted_index.(UKPB). | 35 |
| abstract_inverted_index.bounded | 33 |
| abstract_inverted_index.covered | 225 |
| abstract_inverted_index.density | 112, 125, 131, 184 |
| abstract_inverted_index.divides | 98 |
| abstract_inverted_index.exactly | 168 |
| abstract_inverted_index.maximum | 129, 154, 182 |
| abstract_inverted_index.neither | 63 |
| abstract_inverted_index.problem | 6, 31, 209 |
| abstract_inverted_index.propose | 81 |
| abstract_inverted_index.solving | 43 |
| abstract_inverted_index.usually | 51 |
| abstract_inverted_index.utilize | 134 |
| abstract_inverted_index.$O(R^4)$ | 89 |
| abstract_inverted_index.569-587, | 149 |
| abstract_inverted_index.capacity | 48, 71 |
| abstract_inverted_index.composed | 120, 179 |
| abstract_inverted_index.constant | 17 |
| abstract_inverted_index.criteria | 13 |
| abstract_inverted_index.density, | 193 |
| abstract_inverted_index.equation | 201 |
| abstract_inverted_index.includes | 69 |
| abstract_inverted_index.increase | 39 |
| abstract_inverted_index.knapsack | 5, 30, 47 |
| abstract_inverted_index.leverage | 203 |
| abstract_inverted_index.multiset | 100 |
| abstract_inverted_index.referred | 25 |
| abstract_inverted_index.relevant | 204 |
| abstract_inverted_index.required | 219 |
| abstract_inverted_index.specific | 12 |
| abstract_inverted_index.$O(R^3)$. | 94 |
| abstract_inverted_index.Benchmark | 0 |
| abstract_inverted_index.Frobenius | 208 |
| abstract_inverted_index.according | 10 |
| abstract_inverted_index.algorithm | 61, 84, 96, 166, 222 |
| abstract_inverted_index.determine | 152 |
| abstract_inverted_index.generated | 9 |
| abstract_inverted_index.initially | 97 |
| abstract_inverted_index.instances | 1, 22 |
| abstract_inverted_index.primarily | 224 |
| abstract_inverted_index.selection | 155 |
| abstract_inverted_index.transform | 195 |
| abstract_inverted_index.typically | 8 |
| abstract_inverted_index.unbounded | 4, 29 |
| abstract_inverted_index.(B\&B) | 140 |
| abstract_inverted_index.Therefore, | 58 |
| abstract_inverted_index.complexity | 65, 68, 87, 92 |
| abstract_inverted_index.convenient | 233 |
| abstract_inverted_index.difficulty | 41 |
| abstract_inverted_index.first-year | 228 |
| abstract_inverted_index.instances, | 45 |
| abstract_inverted_index.subsequent | 235 |
| abstract_inverted_index.techniques | 218 |
| abstract_inverted_index.Diophantine | 200 |
| abstract_inverted_index.coefficient | 72 |
| abstract_inverted_index.conclusions | 205 |
| abstract_inverted_index.curriculum, | 230 |
| abstract_inverted_index.mathematics | 229 |
| abstract_inverted_index.multisubset | 118, 177 |
| abstract_inverted_index.particular, | 215 |
| abstract_inverted_index.researchers | 236 |
| abstract_inverted_index.Unbounded-DP | 165 |
| abstract_inverted_index.anticipated. | 76 |
| abstract_inverted_index.coefficients | 34 |
| abstract_inverted_index.counterparts | 188 |
| abstract_inverted_index.efficiently. | 213 |
| abstract_inverted_index.multisubsets, | 104 |
| cited_by_percentile_year | |
| corresponding_author_ids | https://openalex.org/A5100397725 |
| countries_distinct_count | 0 |
| institutions_distinct_count | 1 |
| citation_normalized_percentile |