A k-approximation to k-way number partitioning

Question

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?

Answer 1

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.