0
$\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$
10
  • $\begingroup$ I don't understand what you mean by additive k-approximation. $\endgroup$ Commented Nov 22, 2020 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$ Commented Nov 23, 2020 at 11:25
  • 1
    $\begingroup$ The nomenclature "additive $k$-approximation" for what you want is not standard and is not clear. $\endgroup$ Commented Nov 23, 2020 at 23:33
  • 1
    $\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$ Commented Nov 23, 2020 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
    Commented Nov 24, 2020 at 2:26

2 Answers 2

2
$\begingroup$

Here is a detailed elaboration of Chandra's suggestion in the comments, namely that OP's (first) request, for a poly-time algorithm that can pack $S$ into $k$ bins of size at most MinMax$(S, k-\delta)$, is essentially equivalent to asking for a poly-time, additive-$\delta$ approximation algorithm for the well-studied Bin Packing problem.

For Bin Packing, the best additive approximation known to be achievable in polynomial time is OPT${}+O(\log {}$OPT$).$ Consequently, for OP's problem:

  1. There is a poly-time algorithm that packs $S$ into $k$ bins of size at most MinMax$(S, k-O(\log k))$.

  2. It is likely hard to do better, i.e., achieve MinMax$(S, k-o(\log k)$, much less MinMax$(S, k-1).$

Similar results hold w.r.t. multiplicative error bounds. Essentially, bicriteria-approximation algorithms as considered by OP for OP's problem are equivalent to approximation algorithms (in the usual sense) for Bin Packing.

Regarding OP's second request, for a poly-time algorithm that can use $S$ to cover $k$ bins of size at least MaxMin$(S, k+\delta)$, it seems likely that a similar argument shows that the problem is essentially equivalent to asking for a poly-time additive-$\delta$ approximation for Bin Covering. Bin Covering seems slightly harder to approximate than Bin Packing: it is apparently not known whether this is possible even for any $\delta = o(k)$, so finding an algorithm with $\delta=1$ would be a breakthrough.


Lemma 1. Fix any non-decreasing, sub-linear function $f:\mathbb N \to \mathbb N$. There is a poly-time algorithm for OP's problem that guarantees to pack $S$ into $k$ bins of size at most MinMax$(S, k-O(f(k)))$ if and only if there is a poly-time algorithm for Bin Packing that uses at most OPT${}+ O(f($OPT$))$ bins.

Proof. First we show the "only if" direction. Assume there is a poly-time algorithm $A(S, k)$ for OP's problem that guarantees to pack $S$ into $k$ bins of size at most MinMax$(S, k-f(k))$. Here is the approximation algorithm $B$ for Bin Packing (into bins of size 1):


algorithm $B$ on Bin Packing instance $S=(b_1, b_2, \ldots, b_n)$, where $0\le b_i \le 1$ for $i\in [n]$:

  1. for each integer $k\gets 1, 2, \ldots, n$ do:
  2. $~~~$ if the max bin size used by $A(S, k)$ is at most 1:
  3. $~~~~~~$ return the packing of $S$ into $k$ bins achieved by $A(S, k)$
  4. return the trivial packing of the $n$ items into $n$ bins

Next we verify that $B(S)$ returns a packing of size at most OPT${}+O(f($OPT$)). $

  1. Let $k^* = \min \{k : k-f(k) \ge {}$OPT$\}.$

  2. It is possible to pack $S$ into OPT bins of size 1. That is, MinMax$(S, \,$OPT$) {} \le 1$.

  3. So MinMax$(S, k^* - f(k^*)) \le 1$.

  4. So $A(S, k^*)$ can pack $S$ into $k^*$ bins of size at most 1.

  5. So $B(S)$ packs $S$ into at most $k^*$ bins of size 1. (Note this holds even if $k^* > n$.)

  6. The choice of $k^*$ gives $k^* < {}$OPT${} + f(k^* - 1) + 1 = {}$OPT${} + O(f($OPT$))$.

The equality in the last step uses that $f(k)$ is sublinear. This shows the "only if" direction.


Next we show the "if" direction. Assume there is a poly-time algorithm for Bin Packing that guarantees to pack $S$ into at most OPT+$f($OPT$)$ size-1 bins.

For Bin Packing the given numbers are assumed to be rational. For convenience, assume instead that the given numbers are integers, but an additional integer $s$ is given, and the problem is to pack the given numbers into a minimum number of bins of size $s$. (This is without loss of generality: in polynomial time, we can take $s$ to be the product of the denominators of the given numbers, and scale every given number by $s$.) Let $B(S, s)$ denote the assumed Bin Packing algorithm, modified to take inputs in this form.

Likewise, assume in OP's problem that the given numbers are integers. (This is WLOG as OP's problem is invariant under scaling.)

Given an instance $(S=(a_1,\ldots, a_n), k)$ of OP's problem (where $S\subset \mathbb N$), the algorithm will use binary search to find the minimum integer $s'$ such that $B(S, s')$ packs $S$ into at most $k$ bins of size $s'$. It then returns that packing. The binary search is on integers in the range $[1, U],$ where $U=\sum_{i=1}^n a_i$ (so all items can be packed into one bin of size $U$). This specifies the algorithm.

The binary search requires $O(\log U)$ iterations. This is polynomial in the size of the input (in particular, in the number of bits needed to encode all $n$ numbers in $S$). So the algorithm takes polynomial time.


To finish we verify that this $s'$ is at most MaxMin$(S, k - f(k))$.

  1. Let OPT be the minimum number of size-$(s'-1)$ bins needed to pack $S$.

  2. We need to show that MaxMin$(S, k - f(k)) \ge s'$.

  3. Note that this is equivalent to OPT$ {} > k - f(k).$

  4. If OPT${} > k$, we are done, so assume OPT${}\le k.$

  5. $B$'s guarantee and the choice of $s'$ imply OPT${}+f($OPT$) {} > k$, i.e. OPT${} > k - f($OPT$).$

  6. $f$ is non-decreasing and OPT ${} \le k$, so this implies OPT${} > k - f(k)$, as desired.

  7. Per Step 3 above, this completes the proof. $~~~\Box$.

$\endgroup$
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.

$\endgroup$
2
  • $\begingroup$ Is this bound tight for the algorithm? $\endgroup$
    – Neal Young
    Commented Nov 24, 2020 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$ Commented Nov 24, 2020 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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