Multiple-Choice Knapsack with Small Items
summary
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…
In short
This paper presents an O(n + w^4_max) algorithm for solving the Multiple-Choice Knapsack problem, which requires selecting exactly one item from each disjoint class. The method uses a greedy anchor based on upper hulls, a proximity lemma to bound solution deviation, and dynamic programming over total weight changes to find optimal solutions across consecutive capacities.
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 used across episodes
This episode discusses
The paper
Multiple-Choice Knapsack with Small Items · Read on arXiv
Institute of Informatics, University of Warsaw
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.
DOI: 10.4230/LIPIcs.ESA.2026.29
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.
More episodes
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game
- 1905.10490-Finding new routes for integrating Multi-Agent Systems using Apache Camel
- 2401.10816-Co-Pilot for Health: Personalized Algorithmic AI Nudging to Improve Health Outcomes
- 2503.01935-MultiAgentBench: Evaluating the Collaboration and Competition of LLM agents
- 2509.19405-Improving Outdoor Multi-cell Fingerprinting-based Positioning via Mobile Data Augmentation
- 2602.15198-Colosseum: Auditing Collusion in Cooperative Multi-Agent Systems
- 2602.21456-Revisiting Text Ranking in Deep Research
- 2606.02883-LLM-Assisted Reranking to Operationalize Nuanced Objectives in Recommender Systems