Multiple-Choice Knapsack with Small Items

arXiv:2611.15780 · cs.DS · Submitted 2026-11-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Multiple-Choice Knapsack with Small Items".

Jane: Here's the gist of the paper. The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class, and this paper presents an O(n + w 4 max)-time algorithm for solving it Algorithm Overview The main result is that the Multiple-Choice Knapsack problem can be solved in time O(n + w 4 max), where n is the total number of items and wmax is the maximum weight range within a class Moreover, for any capacity c, the algorithm can output optimal objective values for the capacities c, c + 1,..., c + wmax within the same running time The algorithm first computes the upper hull of each class and uses it to construct a greedy anchor Then, it proves a proximity lemma showing that there exists an optimal solution for capacity c that differs from the anchor in only few classes, with bounded total weight increase and decrease Finally, it keeps only the most promising candidates for each possible weight change and runs a dynamic program over the total weight change within a window of size O(w 2 max) Greedy Anchor Construction The greedy anchor is computed from the upper hull of every class, but the final dynamic program in Section 6 still considers the original items Definition 2 defines the weight increment, price increment, and slope of the upgrade from item j - 1 to item j by ∆w i,j = w ij − w i(j−1), ∆p i,j = p ij − p i(j−1), ρ i,j = ∆p i,j / ∆w i,j The greedy procedure starts with the lightest upper-hull item in each class It then processes upper-hull upgrades in non-increasing order of slope This is the intended prefix-by-slope rule Proposition 3 states that the greedy anchor can be computed in O(n) time, and if Algorithm 1 returns g and cg = w(g), then g is an optimal solution for capacity cg in the original instance Proximity Bound and Pruning To control how far an optimal solution can deviate from the greedy anchor, we need a bound on cancellations Lemma 7 shows that there exists an optimal solution j for capacity c such that D>(g, j) w (g, j)) < wmax(wmax − 1), and D<(g, j) ≤ wmax and Σ(D<w (g, j)) ≤ wmax(wmax − 1) Given an anchor g, exchanging the selected item in class i with item (i, j) changes the weight and price by ω ij = w ij − w ig and φ ij = p ij − p ig For every nonzero integer δ ∈

−wmax, wmax: , Gδ is defined as the set of 2wmax items with largest price change φ ij (or all items if the group is smaller) This results in Sg ≤ 4w 2 max Dynamic Programming Implementation The dynamic program around an anchor solution uses a rolling dynamic program over total weight change x ∈

−W, W: , where W = wmax(wmax − 1) After processing some classes, DP(x) stores the maximum total price change achievable with total weight change x The transition for a processed class i is DP'(x + ω) = max(DP'(x + ω), DP(x) + φ) for (ω, φ) ∈ Ci The total time is O(n + w 4 max), and the working space is O(w 2 max) Consecutive Capacities and Applications Corollary 10 states that one run of the dynamic program around h gives optimal values for every capacity cˆ ∈

ch, ch + wmax: This windowed viewpoint leads to applications in bounded-domain (max, +) convolution, including deterministic network calculus The running time of the standard dynamic program for MCKP is O(nc) for integral capacity c, which can be prohibitive when the global budget is large This bound O(n + w 4 max) replaces this dependence on the global budget by wmax = maxi(w ni − w i1), the largest within-class weight range Small Item Prices Variant Assume prices are integers and define pmax = maxi∈

r: (p ni − p i1) The price-based variant mirrors the weight-based approach, but with roles reversed First, the greedy anchor is constructed by following the steepest price-per-weight slopes Second, we group candidate upgrades by their price change ∆p (instead of weight change) and keep, for each ∆p, the 2pmax items with the smallest weight increase This guarantees that the multiset of price changes used by an optimal solution has total price change at most P = pmax(pmax − 1) The resulting symmetric bound is O(n + p 4 max) We presented a pseudopolynomial-time algorithm for MCKP with running time O(n + w 4 max), based on upper-hull greedy anchors, a proximity bound, and a subset-sum separation argument The same dynamic program also yields optimal values for wmax + 1 consecutive capacities An open problem is to match the best known small-item bounds for 0-1 Knapsack and improve the dependence on wmax or pmax for MCKP The class constraint prevents arbitrary combinations and breaks the additive structure that those methods use Applications The algorithm can be interpreted as evaluating a bounded-domain (max, +) convolution In many scenarios one is interested only in values of the convolution within a limited time window This is particularly beneficial when the allocation must be recomputed repeatedly, e.g., across time steps in tracking or as part of a larger mechanism In this setting, an O(n + w 4 max)-time algorithm gives an exact alternative whose running time is controlled by the discretization granularity rather than by the global budget The same bounded-window dynamic program can also be viewed as a routine for bounded-domain (max, +) convolution on consecutive output ranges Deterministic Network Calculus Deterministic network calculus models network elements by service curves and combines them using min-plus convolution After a sign change this operation becomes a (max, +) convolution When service curves are discretized on a bounded time horizon t ∈

0, d: , evaluating end-to-end guarantees reduces to computing such bounded-domain convolutions In many scenarios one is interested only in values of the convolution within a limited time window Bit Allocation and Power Allocation Cao, Brahma, and Varshney study incentive-compatible target tracking via crowdsourcing under a global communication budget Consolini, Medagliani, and Ferrari consider transmit-power allocation in Zigbee wireless sensor networks with a finite total power budget In this setting, an O(n + w 4 max)-time algorithm gives an exact alternative whose running time is controlled by the discretization granularity rather than by the global budget The same set of available power levels per node is typically small, so after discretization the within-class range wmax is small even if the total budget is large Acknowledgments Supported by the National Science Centre (NCN) grant no.

Tom: 2022/47/D/ST6/02184 Supported by the National Science Centre (NCN) grant no.

Jane: 2022/47/D/ST6/02184 The acknowledgments section is present on page 9.

Tom: References

3: Karl Bringmann.

Paper summary: Tom: So, this paper is about the Multiple-Choice Knapsack problem with small items, and it claims they found an algorithm that runs in O(n plus w four max) time. That means it's faster than the standard dynamic programming approach when the item weights within each class are not too large.

Jane: It tackles a problem where you have to pick exactly one item from each class, and the goal is to get the most profit without exceeding a total capacity, which is a generalization of the classic zero-one Knapsack problem <ref:2611.15780#pg2>. The main point here is that for this specific type of problem, they provide an algorithm that can solve it in time proportional to n plus w four max, where w four max is defined as the maximum weight range within any single class, which is maxi of wi minus wi one <ref:2611.15780#pg3>.

Lu: What's interesting about this result is that they don't just give you an answer for one capacity, say a specific capacity c; they can output the optimal values for capacities from c up to c plus w four max within that same running time <ref:2611.15780#pg2>. That's a significant extension of what was previously known about the standard dynamic program running in time proportional to n times c, which is pseudopolynomial because it depends on the capacity itself.

Meng: From a production standpoint, being able to calculate an entire window of optimal solutions around a target capacity is useful if you're dealing with systems that need to make rapid reallocations or track performance over a range of possible loads <ref:2611.15780#pg2>. But what about the actual implementation? How does this O(n plus w four max) time scale when we consider the total number of items n versus how big that weight range, w four max, gets?

Lalam: Well, they start by computing something called a greedy anchor from the upper hull of each class and then use that to prove a proximity lemma <ref:2611.15780#pg2>. This lemma shows that an optimal solution for capacity c is usually very close to this anchor solution, differing in only a few classes with a bounded total weight change <ref:2611.15780#pg2>.

Tom: That sounds like they're trying to limit the search space significantly before running the main dynamic program, which is smart because it reduces the amount of work needed for those changes <ref:2611.15780#pg2>. But how do they define that greedy anchor exactly?

Paper summary: Jane: The greedy anchor construction involves processing items based on their weight increments, price increments, and slopes between items in each class, specifically using a prefix-by-slope rule where they look at the upper hull of each class <ref:2611.15780#pg2>. They define these increments as delta w i j, delta p i j, and rho i j which is the price increment divided by the weight increment <ref:2611.15780#pg3>.

Lu: It's a specific way to order the upgrades in non-increasing order of their slope to build that anchor, and Proposition three states that this greedy anchor can be found in O(n) time <ref:2611.15780#pg2>. If you take the weight of that greedy solution, which they call cg, it's an optimal solution for capacity cg in the original instance <ref:2611.15780#pg2>.

Meng: So they start with a known good point and then use that to prune the rest of the search space? That makes sense if the deviation from that anchor is small, which is where Lemma seven comes in <ref:2611.15780#pg2>. But what does this proximity bound actually look like in terms of how much weight or price can change when you swap out an item?

Jane: Lemma seven gives a bound on the difference between the greedy anchor and any optimal solution j for capacity c, showing that the absolute difference in weight and price is bounded by w max minus one <ref:2611.15780#pg2>. They also use a set G delta for each possible weight change delta in the range of negative w max to positive w max, where G delta contains up to two times w max items with the largest price change for that weight shift <ref:2611.15780#pg2>.

Tom: So they are not just checking all possibilities around the anchor; they are only looking at a specific, small set of promising candidates defined by these groups G delta, which results in a size bound of four w squared max for the total set S g <ref:2611.15780#pg2>. That sounds like a massive reduction in complexity.

Lu: Exactly. This leads to their dynamic program where they use a rolling dynamic program over the total weight change x, which ranges from negative w to positive w, where w is defined as w max times (w max minus one) <ref:2611.15780#pg2>. After processing some classes, DP x stores the maximum total price change achievable with that specific total weight change <ref:2611.15780#pg2>.

Meng: The transition for this dynamic program is DP prime of x plus omega equals the maximum of current DP prime at x plus omega, or the previous DP at x plus phi, where omega and phi are the weight and price changes from an item in class i <ref:2611.15780#pg3>. It's basically a subset sum problem over these bounded changes <ref:2611.15780#pg3>. How much time does this dynamic programming part take on top of the initial anchor construction?

Paper summary: Jane: The total running time for the whole process ends up being O(n plus w four max), which is good because it replaces that earlier dependence on the capacity c with a dependence only on w four max, which is maxi of wi minus wi one <ref:2611.15780#pg2>. This bound is what makes it practical when the global budget or capacity c might be huge.

Tom: It's interesting how they manage to keep the complexity tied to that class-specific weight range rather than the overall size of the knapsack capacity <ref:2611.15780#pg2>. This suggests their method is really optimized for problems where item sizes within groups are somewhat constrained, not just a huge total budget.

Lu: And they also have a symmetric price-based variant if the item prices are integral and the maximum within-class price range, p max, is small <ref:2611.15780#pg2>. In that case, they get an O(n plus p four max) running time by reversing the roles—the greedy anchor follows steepest price-per-weight slopes and they group candidate upgrades by their price change delta p instead of weight change <ref:2611.15780#pg3>.

Meng: So if we're dealing with a scenario where weights are large but prices are small, we can use the price variant instead, which is still controlled by that class-specific range, just using price changes instead of weight changes to define the DP window size <ref:2611.15780#pg2>. What does this mean for deployment?

Jane: It means if you're dealing with a system where the total budget is huge but the variation in item weights or prices within any class is small, this algorithm provides an exact solution much faster than the standard dynamic program <ref:2611.15780#pg2>. It gives you optimal values for consecutive capacities, which can be useful for things like bounded-domain convolution in network calculus <ref:2611.15780#pg4>.

Tom: I wonder what the limitations are here? They mention that the standard dynamic program runs in O(n times c) for integral capacity c, and this new bound replaces that dependence on the global budget with w four max <ref:2611.15780#pg2>. So where does it still stop working efficiently?

Lu: The paper states they didn't find any other pseudopolynomial time algorithm currently known for the general Multiple-Choice Knapsack problem <ref:2611.15780#pg2>. They focus on improving the bounds of what is already possible, not solving a fundamentally different class of problem.

Paper summary: Meng: The main thing I see as a limitation is that this complexity still depends on w four max, which is the maximum weight range within a class <ref:2611.15780#pg3>. If one class has an enormous range of item weights, even if the total number of items n is small, that complexity could blow up <ref:2611.15780#pg3>.

Jane: That's a fair point. And they do mention that for deterministic network calculus, which uses min-plus convolution after a sign change, this approach gives exact results only when you are interested in values within a limited time window of the convolution <ref:2611.15780#pg4>.

Tom: So we're looking at an O(n plus w four max) algorithm for MCKP that finds optimal solutions for a range of capacities, relying on a greedy anchor and a bounded deviation, which is helpful when the total capacity c is too large for standard methods <ref:2611.15780#pg2>.

Lu: And it shows that if you look at the problem through the lens of bounded-domain convolution, this structure lets you control the computational cost by looking only at a window of size w four max <ref:2611.15780#pg4>.

Meng: For someone trying to deploy a system where allocation needs to be recomputed frequently, having an exact solution whose runtime is controlled by that local weight range instead of the entire global budget is a significant practical win <ref:2611.15780#pg4>.

Jane: It seems like the real value here isn't just finding an answer for one capacity c, but having a systematic way to evaluate a whole range of capacities efficiently, which applies to contexts like tracking or power allocation where you might be interested in performance over consecutive time steps <ref:2611.15780#pg4>.

Tom: So the paper "Multiple-Choice Knapsack with Small Items" presents an O(n plus w four max) algorithm that uses a greedy anchor and a proximity lemma to find optimal solutions for multiple consecutive capacities, which is useful when the total capacity is large but the item weights within each class are constrained <ref:2611.15780#pg2>.

Lu: That's it for this paper. It tackles MCKP by leveraging the structure of item classes to achieve a running time that depends on that class weight range instead of the total knapsack capacity, and it provides optimal values for a window of capacities <ref:2611.15780#pg2>.

Meng: And for deployment, this means we can get exact results for consecutive load scenarios with a runtime controlled by the local item variation rather than having to process the entire global budget space <ref:2611.15780#pg4>.

Jane: We'll leave it there today.

Conclusion: Tom: So we're looking at the paper "Multiple-Choice Knapsack with Small Items," and the authors are focusing on improving how we solve this problem when item sizes within each group aren't huge.

Jane: It seems like this work is about taking a standard knapsack problem, where you pick one item from several groups, and finding an algorithm that runs faster when those group sizes have a certain structure.

Tom: Exactly, it’s about the multiple-choice knapsack problem with small items, and the main idea is using a greedy anchor to drastically cut down the search space for that optimization.

Jane: What this means in plain English is they found a way to solve this problem exactly for several different target capacities very quickly when those group sizes are somewhat limited.

Tom: So it’s not just about getting one answer, but getting an entire range of optimal answers—a window of capacities—in time that doesn't depend on how big the total capacity is.

Jane: Right, and they use this idea to connect it to other areas, like how we handle network delay or power allocation in wireless systems where you’re only really interested in a local performance window.

Tom: It suggests that if you’re dealing with systems where the item weights within a class are constrained but the total budget is massive, this method gives you an exact solution instead of running into those huge pseudopolynomial times.

Jane: But there's still that dependency on the maximum weight range in any single group; if one group has wildly different item weights, that complexity can still get high.

Tom: That’s a fair caveat; it’s not a universal fix for every knapsack problem, just a specific structural improvement for this setup.

Jane: So while it doesn't solve the general knapsack problem instantly, it gives us a powerful tool for scenarios where those class-specific weight variations are actually small.

Tom: It does open up new ways to analyze performance over consecutive points in time or load, which is really useful for things like tracking something that moves or power systems adjusting in real time.

Institute of Informatics, University of Warsaw

cs.DS

Submitted: 2026-11-11

Updated: 2026-11-11

Journal ref: LIPIcs.ESA.2026, 29:1-29:12

DOI: 10.4230/LIPIcs.ESA.2026.29

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 79/100

The gist: The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class…

Key concepts

Greedy Anchor Construction
This involves finding an initial good solution by selecting the lightest item from each class's upper hull and then iteratively upgrading selections based on the steepest price-per-weight slopes. This provides a strong starting point for finding an optimal answer quickly.
Proximity Bound and Pruning
This lemma proves that any optimal solution is close to the greedy anchor. It quantifies how much weight and price can change by swapping items, allowing the algorithm to focus its search space efficiently around this anchor.
Dynamic Programming Implementation
A rolling dynamic programming approach tracks the maximum achievable price change for every possible total weight change within a window of size O(w^2_max). This DP step refines the initial greedy solution by considering local changes across classes.
Consecutive Capacities
The algorithm is designed to find optimal objective values not just for one capacity, but for a range of consecutive capacities (c to c + wmax). This property is useful in applications where the required capacity might fluctuate slightly.

Terminology

Summary

The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class, and this paper presents an O(n + w 4 max)-time algorithm for solving it

Algorithm Overview

The main result is that the Multiple-Choice Knapsack problem can be solved in time O(n + w 4 max), where n is the total number of items and wmax is the maximum weight range within a class Moreover, for any capacity c, the algorithm can output optimal objective values for the capacities c, c + 1,..., c + wmax within the same running time The algorithm first computes the upper hull of each class and uses it to construct a greedy anchor Then, it proves a proximity lemma showing that there exists an optimal solution for capacity c that differs from the anchor in only few classes, with bounded total weight increase and decrease Finally, it keeps only the most promising candidates for each possible weight change and runs a dynamic program over the total weight change within a window of size O(w 2 max)

Greedy Anchor Construction

The greedy anchor is computed from the upper hull of every class, but the final dynamic program in Section 6 still considers the original items Definition 2 defines the weight increment, price increment, and slope of the upgrade from item j - 1 to item j by ∆w i,j = w ij − w i(j−1), ∆p i,j = p ij − p i(j−1), ρ i,j = ∆p i,j / ∆w i,j The greedy procedure starts with the lightest upper-hull item in each class It then processes upper-hull upgrades in non-increasing order of slope This is the intended prefix-by-slope rule Proposition 3 states that the greedy anchor can be computed in O(n) time, and if Algorithm 1 returns g and cg = w(g), then g is an optimal solution for capacity cg in the original instance

Proximity Bound and Pruning

To control how far an optimal solution can deviate from the greedy anchor, we need a bound on cancellations Lemma 7 shows that there exists an optimal solution j for capacity c such that D>(g, j) w (g, j)) < wmax(wmax − 1), and D<(g, j) ≤ wmax and Σ(D<w (g, j)) ≤ wmax(wmax − 1) Given an anchor g, exchanging the selected item in class i with item (i, j) changes the weight and price by ω ij = w ij − w ig and φ ij = p ij − p ig For every nonzero integer δ ∈ [−wmax, wmax], Gδ is defined as the set of 2wmax items with largest price change φ ij (or all items if the group is smaller) This results in Sg ≤ 4w 2 max

Dynamic Programming Implementation

The dynamic program around an anchor solution uses a rolling dynamic program over total weight change x ∈ [−W, W], where W = wmax(wmax − 1) After processing some classes, DP(x) stores the maximum total price change achievable with total weight change x The transition for a processed class i is DP'(x + ω) = max(DP'(x + ω), DP(x) + φ) for (ω, φ) ∈ Ci The total time is O(n + w 4 max), and the working space is O(w 2 max)

Consecutive Capacities and Applications

Corollary 10 states that one run of the dynamic program around h gives optimal values for every capacity cˆ ∈ [ch, ch + wmax] This windowed viewpoint leads to applications in bounded-domain (max, +) convolution, including deterministic network calculus The running time of the standard dynamic program for MCKP is O(nc) for integral capacity c, which can be prohibitive when the global budget is large This bound O(n + w 4 max) replaces this dependence on the global budget by wmax = maxi(w ni − w i1), the largest within-class weight range

Small Item Prices Variant

Assume prices are integers and define pmax = maxi∈[r] (p ni − p i1) The price-based variant mirrors the weight-based approach, but with roles reversed First, the greedy anchor is constructed by following the steepest price-per-weight slopes Second, we group candidate upgrades by their price change ∆p (instead of weight change) and keep, for each ∆p, the 2pmax items with the smallest weight increase This guarantees that the multiset of price changes used by an optimal solution has total price change at most P = pmax(pmax − 1) The resulting symmetric bound is O(n + p 4 max)

Conclusion

We presented a pseudopolynomial-time algorithm for MCKP with running time O(n + w 4 max), based on upper-hull greedy anchors, a proximity bound, and a subset-sum separation argument The same dynamic program also yields optimal values for wmax + 1 consecutive capacities An open problem is to match the best known small-item bounds for 0-1 Knapsack and improve the dependence on wmax or pmax for MCKP The class constraint prevents arbitrary combinations and breaks the additive structure that those methods use

Applications

The algorithm can be interpreted as evaluating a bounded-domain (max, +) convolution In many scenarios one is interested only in values of the convolution within a limited time window This is particularly beneficial when the allocation must be recomputed repeatedly, e.g., across time steps in tracking or as part of a larger mechanism In this setting, an O(n + w 4 max)-time algorithm gives an exact alternative whose running time is controlled by the discretization granularity rather than by the global budget The same bounded-window dynamic program can also be viewed as a routine for bounded-domain (max, +) convolution on consecutive output ranges

Deterministic Network Calculus

Deterministic network calculus models network elements by service curves and combines them using min-plus convolution After a sign change this operation becomes a (max, +) convolution When service curves are discretized on a bounded time horizon t ∈ [0, d], evaluating end-to-end guarantees reduces to computing such bounded-domain convolutions In many scenarios one is interested only in values of the convolution within a limited time window

Bit Allocation and Power Allocation

Cao, Brahma, and Varshney study incentive-compatible target tracking via crowdsourcing under a global communication budget Consolini, Medagliani, and Ferrari consider transmit-power allocation in Zigbee wireless sensor networks with a finite total power budget In this setting, an O(n + w 4 max)-time algorithm gives an exact alternative whose running time is controlled by the discretization granularity rather than by the global budget The same set of available power levels per node is typically small, so after discretization the within-class range wmax is small even if the total budget is large

Acknowledgments

Supported by the National Science Centre (NCN) grant no. 2022/47/D/ST6/02184 Supported by the National Science Centre (NCN) grant no. 2022/47/D/ST6/02184 The acknowledgments section is present on page 9. p. 0

Where the paper says it

Besides the standard dynamic program running in time O(nc), where n is the total number of items and c is the knapsack capacity, no other pseudopolynomialtime algorithm is currently known. We present an O(n + w 4 max)-time algorithm, where wmax = maxi(wini − wi1) is the maximum weight range within a class.

References

[3] Karl Bringmann. Knapsack with small items in near-quadratic time. p. 0

Where the paper says it

Multiple-Choice Knapsack with Small Items Jakub Pawlewicz Institute of Informatics, University of Warsaw, Poland pan@mimuw. pl ORCID: 0000-0003-4670-9106 Abstract The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class.

In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), 2024

[9] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. p. 0

Where the paper says it

MCKP appears in applications such as resource allocation, project selection, and communication systems; see the survey by Szkaliczki [12] for a recent overview or the book by Kellerer et al. [9, Chapter 11] for comprehensive coverage of Multiple-Choice Knapsack and related problems.

p. 0
Where the paper says it

MCKP appears in applications such as resource allocation, project selection, and communication systems; see the survey by Szkaliczki [12] for a recent overview or the book by Kellerer et al. [9, Chapter 11] for comprehensive coverage of Multiple-Choice Knapsack and related problems.

Springer Berlin Heidelberg, 2004

[8] Ce Jin. 0-1 knapsack in nearly quadratic time. p. 0

Where the paper says it

pl ORCID: 0000-0003-4670-9106 Abstract The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class. Besides the standard dynamic program running in time O(nc), where n is the total number of items and c is the knapsack capacity, no other pseudopolynomialtime algorithm is currently known.

p. 0
Where the paper says it

pl ORCID: 0000-0003-4670-9106 Abstract The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class. Besides the standard dynamic program running in time O(nc), where n is the total number of items and c is the knapsack capacity, no other pseudopolynomialtime algorithm is currently known.

In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), 2024

[11] Adam Polak, Lars Rohwedder, and Karol Węgrzycki. Knapsack and subset sum with small items. p. 4

Where the paper says it

If these multisets shared a nonzero common subset sum, we could exchange those classes and contradict the minimality argument in the proximity proof. The following elementary pigeonhole lemma is the same kind of subset-sum separation used by Polak, Rohwedder, and Węgrzycki for 0-1 Knapsack [11, Lemma 2.

In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of LIPIcs, pages 106:1–106:19

[3] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. p. 3

Where the paper says it

Let w0 = Pr i=1 wi1 and B = c−w0 be the upgrade budget. A linear-time weighted selection on the slopes [1] finds a threshold τ such that all upgrades with slope larger than τ fit, while not all upgrades with slope at least τ fit.

Journal of Computer and System Sciences, 7(4):448–461, August 1973

[2] Jean-Yves Le Boudec and Patrick Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. p. 0

Where the paper says it

In Section 8 we discuss representative examples including bit allocation for crowdsourcing-based target tracking and discrete transmit-power control in Zigbee sensor networks [4, 5]. We also note that the same dynamic-programming machinery yields bounded-domain (max, +) convolution on consecutive ranges, which connects to deterministic network calculus [6, 2].

Springer, 2001

[4] Nianxia Cao, Swastik Brahma, and Pramod K. Varshney. Target tracking via crowdsourcing: A mechanism design approach. p. 9

Where the paper says it

In such cases the windowed computation enabled by our algorithm can reduce the running time when the number of network elements is large but the discretization horizon is moderate. 3 Bit allocation under a global communication budget Cao, Brahma, and Varshney study incentive-compatible target tracking via crowdsourcing under a global communication budget.

IEEE Transactions on Signal Processing, 63(6):1464–1476, 2015

[5] Luca Consolini, Paolo Medagliani, and Gianluigi Ferrari. Adjacency matrix-based transmit power allocation strategies in wireless sensor networks. p. 9

Where the paper says it

, across time steps in tracking or as part of a larger mechanism. 4 Transmit-power allocation with discrete power levels Consolini, Medagliani, and Ferrari consider transmit-power allocation in Zigbee wireless sensor networks with a finite total power budget.

Sensors, 9(7):5390–5422, 2009

[6] René L. Cruz. A calculus for network delay, part i: Network elements in isolation. p. 9

Where the paper says it

In many scenarios one is interested only in values of the convolution within a limited time window (for example when testing deadline feasibility or during parametric search for delay bounds). In such cases the windowed computation enabled by our algorithm can reduce the running time when the number of network elements is large but the discretization horizon is moderate.

IEEE Transactions on Information Theory, 37(1):114–131, 1991

[7] Krzysztof Dudziński and Stanisław Walukiewicz. Exact methods for the knapsack problem and its generalizations. p. 1

Where the paper says it

While MCKP is closely related to 0-1 Knapsack, standard reductions do not preserve the structural regimes exploited by the fastest “small item” algorithms. In particular, normalizing by the lightest item in each class creates upgrade items but also introduces a per-class restriction (at most one upgrade per class), which breaks the unrestricted mixing of items that those methods rely on.

European Journal of Operational Research, 28(1):3–21, January 1987

[8] Ce Jin. 0-1 knapsack in nearly quadratic time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), 2024

[9] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer Berlin Heidelberg, 2004

[10] Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. p. 0

Where the paper says it

Multiple-Choice Knapsack with Small Items Jakub Pawlewicz Institute of Informatics, University of Warsaw, Poland pan@mimuw. pl ORCID: 0000-0003-4670-9106 Abstract The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class.

Pattern matching and consensus problems on weighted sequences and profiles. p. 0
Where the paper says it

MCKP also arises in string algorithmics, e. , in weighted pattern matching and consensus problems on weighted sequences and profiles [10].

Theory of Computing Systems, 63(3):506–542, August 2018

[12] Tibor Szkaliczki. Solution methods for the multiple-choice knapsack problem and their applications. p. 0

Where the paper says it

MCKP appears in applications such as resource allocation, project selection, and communication systems; see the survey by Szkaliczki [12] for a recent overview or the book by Kellerer et al. [9, Chapter 11] for comprehensive coverage of Multiple-Choice Knapsack and related problems.

Mathematics, 13(7), 2025

--- Page 9 ---

The acknowledgments section is present on page 9.

--- Page 8 ---

The acknowledgments section is present on page 9.

--- Page 7 ---

The acknowledgments section is present on page 9.

--- Page 6 ---

The acknowledgments section is present on page 9.

--- Page 5 ---

The acknowledgments section is present on page 9.

--- Page 4 ---

The acknowledgments section is present on page 9.

--- Page 3 ---

The acknowledgments section is present on page 9

--- Page 2 ---

The acknowledgments section is present on page 9

--- Page 1 ---

The acknowledgments section is present on page 9.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Bounded-domain convolution capability: The algorithm can be interpreted as evaluating a bounded-domain (max, +) convolution, allowing it to compute values of F(x) on d + 1 consecutive points in O(dk + d4) time, improving upon the classical O(skd) dynamic programming approach when k is much larger than d2.

  2. Consecutive capacity optimization: The algorithm yields optimal values for wmax plus 1 consecutive capacities starting from an anchor solution, which can be efficiently extended to cover a full range of capacities c through a single or twice additional runs of the dynamic program.

  3. Bounded price variant implementation: When item prices are integral and the maximum within-class price range pmax is small, the algorithm achieves a symmetric price-based variant running in O(n + p4max) time, providing an efficient solution for scenarios with constrained benefit ranges.

  4. Application in discrete resource allocation: The algorithm can be applied to problems like Zigbee wireless sensor networks where nodes select one transmit power from a small set under a global power constraint, offering an exact alternative whose running time is controlled by the discretization granularity rather than the global budget.

  5. Time and space efficiency for large budgets: By replacing the dependence on the global budget c with wmax = maxi(wini − wi1), the algorithm provides a running time of O(n + w4max) for MCKP, which is crucial when budgets are large but within-class ranges are small, such as in bit allocation under a global communication budget.

Abstract

The Multiple-Choice Knapsack problem is a generalization of the Knapsack problem in which items are partitioned into disjoint classes and exactly one item must be selected from each class. Besides the standard dynamic program running in time O(nc), where n is the total number of items and c is the knapsack capacity, no other pseudopolynomial-time algorithm is currently known. We present an O(n+w 4) -time algorithm, where w= i (w in i-w i1) is the maximum weight range within a class.

Related papers