1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't understand what you mean by additive k-approximation. $\endgroup$ – Chandra Chekuri Nov 22 at 16:37
  • $\begingroup$ @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? $\endgroup$ – Erel Segal-Halevi Nov 23 at 11:25
  • $\begingroup$ The nomenclature "additive $k$-approximation" for what you want is not standard and is not clear. $\endgroup$ – Chandra Chekuri Nov 23 at 23:33
  • $\begingroup$ 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 $\endgroup$ – Chandra Chekuri Nov 23 at 23:36
  • $\begingroup$ 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)$. $\endgroup$ – Neal Young Nov 24 at 2:26
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.