The Exact One-Half Threshold for Arbitrary-Capacity Bottleneck Multiple Subset Sum

Introduction

Background and the source problem

Packing as much material as possible and ensuring that every container receives a substantial amount are different objectives. The latter leads to bottleneck multiple subset sum: each item has a nonnegative weight, each knapsack has a capacity, and disjoint subsets of items are assigned to maximize the smallest total load. Items may remain unpacked. The objective is an absolute load, not a fraction of the receiving knapsack’s capacity. For identical capacities, Caprara, Kellerer, and Pferschy [1] established the exact polynomial-time approximation threshold $2/3$, under $P \ne NP$.

Allowing different capacities changes which combinations of items can be assigned to which knapsacks. Chen et al. [3] study the more general bottleneck multiple knapsack problem, where profits and weights are independent. Their Theorems 2–3 give a $(1/2 - \varepsilon)$-approximation for arbitrary capacities and hardness above $1/2$, already with unit profits. Their published concluding Section 7 then asks whether the special case with profit equal to weight retains the identical-capacity guarantee:

The same discussion asks the following separate question.

These questions have different histories. The unit-profit problem is the older problem of maximizing the minimum number of pieces in unequal bins. Friesen and Langston [4] already proved a $1/2$ guarantee with zero additive loss using a first-fit-decreasing implementation, together with hardness of every larger ratio with zero additive loss. The unit-profit proof below is an alternative elementary argument for that known result. The main subject of this note is the first question, for profits equal to weights.

Contribution

The arbitrary-capacity threshold for bottleneck MSSP is $1/2$. The two parts of this assertion are proved separately.

1. Theorem 3.6 gives a $1/2$-approximation using $O(n\log(n+1)+m\log(m+1))$ arithmetic and comparison operations and $O(n+m)$ space on rational inputs, with no $\varepsilon$ loss.

2. Theorem 4.2 excludes every fixed ratio greater than $1/2$, unless P = NP; the real-ratio extension is made explicit in Corollary 4.4. In particular, the $2/3$ guarantee in the first question cannot hold for arbitrary capacities. Corollary 4.3 shows that this obstruction persists when both the capacities and the item weights have arbitrarily small relative spread.

The algorithm separates the two ways a knapsack can receive half a target load $T$. A single item of weight at least $T/2$ suffices, but may fit only some knapsacks. A maximum bipartite matching assigns as many such items as possible. The unmatched knapsacks are filled using only items of weight less than $T/2$; adding these items until a load first reaches $T/2$ keeps the load below $T$. Thus, if all capacities are at least $T$, sufficient total small-item weight can fill the unmatched knapsacks without violating capacity.

More precisely, if $q_T$ is the maximum matching size and $W_T$ is the total small-item weight, the sufficient condition is

An optimal assignment itself certifies this inequality at $T=\mathrm{OPT}$: choose one big item in every knapsack containing one, and count the small weight in the other knapsacks. The neighborhoods in the matching graph are nested by item weight. Scanning the items from heaviest to lightest and assigning each fitting item to the largest unused capacity computes the maximum matching size for every suffix in one pass. The item classes change only at the $O(n)$ breakpoints $2w_i$. With the strict-small convention, these give intervals $(a,b]$ on which the certificate is linear in $T$ and its largest feasible value is attained. Prefix sums and the suffix matching sizes therefore find the largest certified rational target in linear time after sorting. Neither denominator scaling nor a general matching algorithm is required. For example, capacities 5, 8 and weights 6, 2, 2, 1 certify $T=5$. The big item 6 is assigned to capacity 8, while the small items have total weight 5; two weight-2 items already raise the other knapsack past $T/2$.

The hardness proof uses a different aspect of heterogeneous capacities: they encode prescribed pair sums. A balanced Numerical Matching with Target Sums instance [5 Problem SP17, p. 224] is embedded using low weights $A+x_i$, high weights $A+D+y_i$, and capacities $2A+D+b_j$. An assignment above a suitable threshold must use exactly two items per knapsack. High–high pairs do not fit; counting then forces one low and one high item in every knapsack. Equality of total weight and total capacity forces every pair to meet its prescribed sum. A large common offset makes the no-instance/yes-instance ratio arbitrarily close to $1/2$. This proves hardness within the profit-equals-weight subclass, which does not follow merely from hardness for unrestricted profits. The common offset can also make all capacities, and separately all item weights, arbitrarily close in relative terms. Thus the change from the identical-capacity threshold is already present under arbitrarily small capacity variation; it does not require very large and very small knapsacks in the same instance.

§ 5 gives the short sorted-block argument for the classical unit-profit endpoint (Theorem 5.2). Its prefix-count proof explains why $|\mathrm{OPT}/2|$ items can be placed in every knapsack after sorting both capacities and weights. The matching certificate and numerical-matching reduction establish the main MSSP threshold.

Related work and the role of the objective

Covering problems. Maximizing the minimum load is the covering counterpart of scheduling and bin packing. In machine covering, all jobs must be assigned to machines without capacities and the minimum completion time is maximized; Deuermeyer, Friesen and Langston analyzed the LPT rule [6], and Woeginger gave a PTAS [7]. In bin covering, one maximizes the number of bins whose load reaches a common threshold; Assmann, Johnson, Kleitman and Leung introduced the problem [8], and Jansen and Solis-Oba gave an asymptotic FPTAS [9]. Bottleneck multiple subset sum differs from both: every knapsack has an upper capacity, items may be discarded, and the guarantee concerns the worst knapsack.

Max-sum packing. The max-sum version of multiple subset sum has a different approximation landscape. Caprara, Kellerer, and Pferschy give a PTAS for identical capacities [1] and, in a companion paper, for different capacities [2]. Chekuri and Khanna [10] extend the PTAS conclusion to multiple knapsack with independent profits and weights. These schemes maximize total packed profit. Losing the contents of one knapsack can cause a small relative loss in that total and still destroy a minimum-load guarantee, so these theorems do not settle the bottleneck question.

Fair allocation. The max-min objective also appears in fair allocation. Bansal and Sviridenko [11] study allocation with resource values that may depend on the recipient, without the individual weight-capacity constraints used here. Hummel [12] obtains algorithmic 2/5 maximin-share guarantees for hereditary and budget-constrained valuations, using sufficiently accurate polynomial-time valuation oracles. With a common capacity and common item profits, the maximin-share benchmark agrees with the bottleneck optimum, explaining its connection to identical-capacity BMKP. With different budgets, each agent’s maximin share is a separate benchmark and should not be identified with the common optimum considered here. Rohwedder, Rouhani, and Wennmann [13] instead impose a single global budget on allocation costs in their Budgeted Santa Claus problem. That budget constraint is also distinct from imposing a separate load bound on every knapsack.

Against this background, the result here supplies the exact 1/2 endpoint for arbitrary-capacity MSSP and transfers the hardness threshold into this restricted subclass. For general profits, the (1/2−$\varepsilon$) algorithm of Chen et al. uses rounding and configuration and assignment linear programs [3 Section 5 of the full version]; the equality of profit and weight makes the simple matching-and-filling certificate possible here.

Models and notation

Let $I$ be a finite item set and let $K = \{1,\ldots,m\}$ be the knapsack set, where $m \ge1$. Item $i$ has nonnegative weight $w_i$ and nonnegative profit $p_i$; knapsack $j$ has nonnegative capacity $B_j$. A feasible assignment consists of pairwise disjoint sets $S_j \subseteq I$ such that

Its bottleneck value is $\min_{j}\sum_{i\in S_j} p_i$, and OPT denotes the maximum such value.

For a maximization problem, an algorithm has approximation ratio $\alpha\in[0,1]$ if it always returns a feasible solution of value at least $\alpha$ OPT. Arithmetic inputs are binary-encoded rationals.

In the unit-profit model, $p_i = 1$ for every item, so the value is $\min_j |S_j|$. In bottleneck MSSP, $p_i = w_i$, so the value is the minimum assigned load. All algorithms below work directly with rational input. An arithmetic or comparison operation on these numbers counts as one operation in the stated running times; their bit costs are discussed separately. No bound on the magnitudes of the weights or capacities is assumed.

Multiple subset sum: half-certifiable targets

Fix a target $T > 0$. Call item $i$ small if $w_i \le T/2$ and big otherwise. Let $W_T$ be the total weight of the small items. Form a bipartite graph $G_T$ whose left side consists of the big items and whose right side consists of the knapsacks; join item $i$ to knapsack $j$ when $w_i \le B_j$. Let $q_T$ be the size of a maximum matching in $G_T$.

Proof. If $B_{\min}=0$, no positive target is certified. Otherwise discard zero-weight items and retain the positive weights in their sorted order as in Lemma 3.4. Compute the suffix matching sizes $q_i$ and prefix sums $P_j=\sum_{i=1}^{j}w_i$, including $P_0=0$.

Form the distinct sorted breakpoints

Consecutive breakpoints $a<b$ give intervals $(a,b]$ partitioning $(0,B_{\min}]$. Throughout such an interval, an item is small precisely when $2w_i\le a$: indeed, there is no breakpoint strictly between $a$ and $b$, and an item with $2w_i=b$ is still big at $T=b$. Thus the small items form a fixed prefix, say of length $j$, and

If $q_{j+1}=m$, the interval contributes the certified target $b$. Otherwise its largest certified target is

provided $c>a$; if $c\le a$, the interval contains no certified target. The right endpoint convention ensures that every nonempty feasible portion has a largest element.

There are at most $n+1$ intervals. A monotone pointer through the sorted weights identifies all their prefix lengths in total $O(n)$ operations; each candidate then requires constant work. Returning the largest contributing candidate gives the asserted maximum. All values are computed exactly as rational numbers.

Proof. If $B_{\min}=0$, return the empty assignment. Otherwise sort the weights and capacities, retaining original item and knapsack indices, and apply Lemma 3.5. If no positive target is half-certifiable, then $\mathrm{OPT}=0$ by Lemma 3.3, and the empty assignment suffices.

Let $T^*$ be the largest target found when one exists. Its certificate and Lemma 3.2 imply that a positive-valued assignment exists. Consequently Lemma 3.3 applies and gives $T^*\ge\mathrm{OPT}$. Recover a maximum matching for the suffix of items with $2w_i\ge T^*$ using Lemma 3.4, and greedily fill the unmatched knapsacks as in Lemma 3.2. The resulting value is at least $T^*/2\ge\mathrm{OPT}/2$.

Sorting takes the stated number of comparisons. Prefix sums, suffix matching, interval optimization, matching reconstruction, and filling all take $O(n+m)$ further operations and space. Apart from multiplication or division by two, the rational numbers used are input values, sums of at most $n$ input weights, or such sums divided by an integer at most $m$. Their numerators and denominators have polynomial bit length in the binary input length. Exact arithmetic and comparisons therefore give polynomial bit complexity as well.

Hardness above one half for multiple subset sum

We use Numerical Matching with Target Sums, a strongly NP-complete problem listed by Garey and Johnson [5 Appendix A, Problem SP17, p. 224]. An instance consists of positive integers

and asks whether there are permutations $\pi,\sigma$ of $[q]$ such that

A yes-instance necessarily satisfies $\sum_i x_i+\sum_i y_i=\sum_j b_j$, but this equality is not part of the standard input promise. For the reduction below, preprocess an unequal-sum instance to the fixed balanced no-instance

Both sides have total sum four, while the target one cannot be expressed as a sum of two positive integers. Equal-sum instances are left unchanged. Thus the preprocessed instance is balanced and has the same yes/no answer.

No two high items fit together, since $2A+2D>2A+D+U\ge\max_j B_j$. If $p_{LL},p_{LH},p_{HH}$ count the three pair types, this first shows $p_{HH}=0$. Use of all $q$ low and $q$ high items also gives

Therefore $p_{LL}=p_{HH}=0$, and every knapsack contains one low and one high item.

The total item weight equals

All items are used and no capacity is exceeded, so every knapsack is filled exactly. If knapsack $j$ contains the items associated with $x_i$ and $y_k$, exact filling yields $x_i+y_k=b_j$. These pairs solve the NMTS instance, so every assignment of value greater than $H$ induces an NMTS solution.

Consequently, in a negative NMTS instance every assignment has value at most $H$, whereas in a positive instance the optimum is $T$ and $H<\alpha T$. An $\alpha$-approximation would distinguish the two cases in polynomial time.

Proof. In Lemma 4.1, choose the fixed rational $\rho$ small enough that also $\rho<\gamma/2$, and increase the fixed integer $C$ so that also $C>2/\gamma$. All inequalities used in Theorem 4.2 remain valid. Its reduction already uses exactly two items per knapsack. Since $A=C(U+1)$ and $D=\lceil\rho A\rceil$, the capacity ratio satisfies

Every item has weight at least $A$ and at most $A+D+U$, so

The same yes/no gap therefore proves the claim on the restricted instances.

Proof. Theorem 3.6 attains $1/2$, while Theorem 4.2 excludes every fixed larger rational ratio. If an algorithm guaranteed any fixed real ratio $\gamma>1/2$, then choosing a rational $\alpha\in(1/2,\min\{\gamma,1\}]$ would contradict the theorem.

A short alternative proof for unit profits

Under unit profits, BMKP is the max–min cardinality packing problem studied by Friesen and Langston [4]. For unequal bin capacities they gave a polynomial-time FFD implementation with absolute ratio $1/2$, and proved that no larger ratio with zero additive loss is possible unless P = NP. The sorted-block proof below is different and particularly short.

Order the capacities and item weights as

For an integer $q\ge0$ with $mq\le n$, the $q$-block assignment gives knapsack $r$ the items of ranks $(r-1)q+1,\ldots,rq$. Prefix sums test its feasibility in $O(m)$ time. The $0$-block is the empty assignment.

Proof. Delete items from the reference assignment until each knapsack contains exactly $2q-1$ items. Denote the resulting pairwise disjoint item sets by $O_1,\ldots,O_m$, indexed in nondecreasing order of capacity.

Run the block algorithm greedily. Immediately before it fills knapsack $r$, exactly $q(r-1)$ items have been removed. The union $O_1 \cup\cdots\cup O_r$ originally contains $r(2q-1)$ items, so at least

of them remain. Hence some $O_s$ with $s \le r$ still contains at least $q$ items. Choose any $q$ of those items. Their total weight is at most $B_s$, and therefore at most $B_r$. The greedy block consists of the $q$ lightest remaining items, so its total weight is no larger. Thus knapsack $r$ is filled feasibly. The argument applies at every step.

Proof. Test all block sizes $q=0,1,\ldots,\lfloor n/m\rfloor$ and return the largest feasible one, say $Q$. Let $T=\operatorname{OPT}$. If $T=0$, the claim is immediate. Otherwise $T$ is a positive integer, $mT \le n$, and

Thus $q^*$ is among the tested values. Since $2q^*-1 \le T$, Lemma 5.1 shows that the $q^*$-block assignment is feasible. Consequently $Q \ge q^* \ge T/2$.

After sorting and computing prefix sums, all block tests together take $O(n+m)$ arithmetic and comparison operations: there are at most $\lfloor n/m\rfloor+1$ values of $q$, each tested on $m$ knapsacks. The total running time is $O(n\log n+m\log m)$ arithmetic and comparison operations. With binary-encoded rational weights and capacities, every prefix sum has polynomial bit length, so the bit complexity is polynomial as well.

Proof. The lower bound follows from feasibility. If $Q < \lfloor n/m\rfloor$, then the $(Q+1)$-block assignment is infeasible. The contrapositive of Lemma 5.1, with $q=Q+1$, yields $\operatorname{OPT}<2Q+1$, hence $\operatorname{OPT}\le2Q$ because $\operatorname{OPT}$ is integral. If $Q=\lfloor n/m\rfloor$, the item count itself gives $\operatorname{OPT}\le\lfloor n/m\rfloor=Q$.

Example 5.4. Take capacities 10, 10 and four unit-profit items of weights 4, 4, 6, 6. Pairing a 4 with a 6 in each knapsack gives optimum value two. The two-block assignment instead uses blocks (4, 4) and (6, 6) and is infeasible, whereas the one-block assignment is feasible. Thus the algorithm can return one when the optimum is two.

Concluding remarks

Chen et al. [3 Section 7, p. 60:18] also ask for a $(2/3-\varepsilon)$-approximation when the number of distinct capacities is bounded by a constant. The reduction above uses a potentially growing number of capacity values and therefore does not settle that question.