# A k-approximation to k-way number partitioning

The $$k$$-way number partitioning problem accepts as input a multiset $$S$$ of positive numbers, and returns a partition of $$S$$ into $$k$$ subsets such that the subset sums are as nearly-equal as possible, namely,

• the largest sum is as small as possible, or -
• the smallest sum is as large as possible.

Both problems are NP-hard even for $$k=2$$. Denote the optimal solutions of both problems by $$MinMax(S,k)$$ and $$MaxMin(S,k)$$ respectively. Note that both are weakly-decreasing functions of $$k$$. Are there polynomial-time algorithms that find a partition of $$S$$ into $$k$$ subsets such that -

• the largest sum is at most $$MinMax(S,k-1)$$, or -
• the smallest sum is at least $$MaxMin(S,k+1)$$?

The Wikipedia page on number partitioning describes many polynomial-time approximation algorithms for this problem, but they have guarantees of different forms - at most $$(1+\epsilon)\cdot MinMax(S,k)$$ or at least $$(1-\epsilon)\cdot MaxMin(S,k)$$.

There are also algorithms that give constant-factor approximations to the related problems of bin packing and bin covering. Using these algorithms and binary search, I think it is possible to find approximations to number partitioning in weakly-polynomial time. However, the guarantees would be of the form $$MinMax(S,k/(1+\epsilon))$$ or $$MaxMin(S,k/(1-\epsilon))$$, where $$\epsilon$$ is the corresponding approximation factor.

is it possible to attain in polynomial time, an additive $$k$$-approximation?

• I don't understand what you mean by additive k-approximation. – Chandra Chekuri Nov 22 '20 at 16:37
• @ChandraChekuri In the max-min problem, by "additive k-approximation" I mean a k-partition in which the smallest subset sum is at least the smallest subset sum in an optimal (k+1)-partition. It is a "k-approximation" since the approximated factor is the number of subsets k, rather than the sum itself. It is "additive" since the approximation is attained by adding 1 to k, rather than by multiplying it by a factor. Is there a more standard term for this? – Erel Segal-Halevi Nov 23 '20 at 11:25
• The nomenclature "additive $k$-approximation" for what you want is not standard and is not clear. – Chandra Chekuri Nov 23 '20 at 23:33
• Your question for MinMax is related to well-known open problem in bin packing on additive approximation. Can one obtain a solution to bin packing using OPT + c bins for some fixed c? Even c=1 is open which corresponds to your question. See paper of Rothvoss for best known additive approximation and some pointers. arxiv.org/abs/1301.4010 – Chandra Chekuri Nov 23 '20 at 23:36
• What about the a greedy algorithm that considers the items in $S$ by decreasing weight and puts each item in the least-loaded bin? For $k=3$, at least, I think one can prove that its largest bin will have weight at most $\text{MinMax}(S, 2)$. – Neal Young Nov 24 '20 at 2:26

This is not an answer - it is just a reply to Neal Young's comment regarding the greedy algorithm. I claim that in the outcome of the greedy algorithm:

1. The largest sum is at most $$\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$$;
2. The smallest sum is at least $$\operatorname{MaxMin}(S, 2k-1)$$.

Proof. Let $$X_1,\ldots,X_k$$ be the outcome of the greedy algorithm. It is sufficient to prove the claims for an arbitrary subset from this partition, say for $$X_1$$. For any set $$X$$, denote by $$v(X)$$ the sum of numbers in $$X$$.

Proof of 1. Let $$Z_1,\ldots,Z_{\lfloor(k+1)/2\rfloor}$$ be a min-max partition. If $$X_1$$ contains a single item, then it is contained in at least one $$Z_i$$, so $$v(X_1)\leq \max_i v(Z_i)$$. Otherwise, let $$x_1$$ be the last item added to $$X_1$$. By the greedy algorithm definition, both $$v(x_1)$$ and $$v(X_1\setminus \{x_1\})$$ are smaller than $$v(X_2),\ldots,v(X_k)$$. So in the $$(k+1)$$-partition $$\{x_1\},X_1\setminus \{x_1\},X_2,\ldots,X_k$$, the first two elements are smallest. Therefore, their sum is at most $$2/(k+1)$$ of the total: \begin{align*} v(X_1) \leq \frac{2}{k+1}v(S) \end{align*} On the other hand: \begin{align*} \max_i v(Z_i) \geq \frac{1}{\lfloor(k+1)/2\rfloor}v(S) \geq \frac{2}{k+1}v(S) \end{align*} Therefore, $$v(X_1)\leq \max_i v(Z_i)$$ too.

Proof of 2. Let $$x_2,\ldots,x_k$$ be the last item added to $$X_2,\ldots,X_k$$ respectively. By the greedy algorithm definition, if we remove $$x_2,\ldots,x_k$$ from $$X_2,\ldots,X_k$$, then $$v(X_1)$$ is largest among the remaining subsets. Therefore, \begin{align*} v(X_1)\geq \frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\}) \end{align*}

Let $$Y_1,\ldots, Y_{2k-1}$$ be an optimal $$(2k-1)$$ partition. The items $$x_i$$ belong to at most $$n-1$$ sets in the partition $$Y$$, so there are at last $$n$$ sets in that partition that do not contain any $$x_i$$; denote them by $$Y_1,\ldots,Y_k$$. So \begin{align*} \min_{i=1}^{2k-1} v(Y_i) \leq \min_{i=1}^{k} v(Y_i) \leq \frac{1}{k}v(Y_1\cup\cdots \cup Y_k) \leq \frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\}) \end{align*} Therefore, $$v(X_1)\geq \min_i v(Y_i)$$.

So the greedy algorithm is a 2-approximation. The question of whether there exists an additive approximation remains open.

• Is this bound tight for the algorithm? – Neal Young Nov 24 '20 at 13:01
• @NealYoung good question. I tried to find an example for tightness but failed. Perhaps the greedy algorithm attains better than 2-approximation. – Erel Segal-Halevi Nov 24 '20 at 17:47