<p>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 <span class="math-container">$S$</span> into <span class="math-container">$k$</span> bins of size at most MinMax<span class="math-container">$(S, k-\delta)$</span>, is essentially equivalent to asking for a poly-time, additive-<span class="math-container">$\delta$</span> approximation algorithm for the well-studied Bin Packing problem.</p>
<p>For Bin Packing, the <a href="https://en.wikipedia.org/wiki/Bin_packing_problem#Additive_approximation" rel="nofollow noreferrer">best additive approximation known</a>
to be achievable in polynomial time is OPT<span class="math-container">${}+O(\log {}$</span>OPT<span class="math-container">$).$</span>   Consequently, for OP's problem:</p>
<ol>
<li><p>There is a poly-time algorithm that packs <span class="math-container">$S$</span> into <span class="math-container">$k$</span> bins of size at most MinMax<span class="math-container">$(S, k-O(\log k))$</span>.</p>
</li>
<li><p>It is likely hard to do better, i.e., achieve MinMax<span class="math-container">$(S, k-o(\log k)$</span>, much less MinMax<span class="math-container">$(S, k-1).$</span></p>
</li>
</ol>
<p>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.</p>
<p>Regarding OP's second request, for a poly-time algorithm that can use <span class="math-container">$S$</span> to cover <span class="math-container">$k$</span> bins of size at least MaxMin<span class="math-container">$(S, k+\delta)$</span>, it seems likely that a similar argument shows that the problem is essentially equivalent to asking for a poly-time additive-<span class="math-container">$\delta$</span> approximation for Bin Covering.  Bin Covering seems slightly harder to approximate than Bin Packing: it is apparently <a href="https://cstheory.stackexchange.com/questions/50995/is-logarithmic-additive-approximation-to-bin-covering-possible">not known</a> whether this is possible even for any <span class="math-container">$\delta = o(k)$</span>,
so finding an algorithm with <span class="math-container">$\delta=1$</span> would be a breakthrough.</p>
<hr />
<p><strong>Lemma 1.</strong> <em>Fix any non-decreasing, sub-linear function <span class="math-container">$f:\mathbb N \to \mathbb N$</span>.
There is a poly-time algorithm for OP's problem that guarantees to pack <span class="math-container">$S$</span> into <span class="math-container">$k$</span> bins of size at most MinMax<span class="math-container">$(S, k-O(f(k)))$</span>
if and only if there is a poly-time algorithm for Bin Packing that uses at most OPT<span class="math-container">${}+ O(f($</span>OPT<span class="math-container">$))$</span> bins.</em></p>
<p><em>Proof.</em> First we show the &quot;only if&quot; direction.  Assume there is a poly-time algorithm <span class="math-container">$A(S, k)$</span> for OP's problem that guarantees to pack <span class="math-container">$S$</span> into <span class="math-container">$k$</span> bins of size at most MinMax<span class="math-container">$(S, k-f(k))$</span>.
Here is the approximation algorithm <span class="math-container">$B$</span> for Bin Packing (into bins of size 1):</p>
<hr />
<p>algorithm <span class="math-container">$B$</span> on Bin Packing instance <span class="math-container">$S=(b_1, b_2, \ldots, b_n)$</span>, where <span class="math-container">$0\le b_i \le 1$</span> for <span class="math-container">$i\in [n]$</span>:</p>
<ol>
<li>for each integer <span class="math-container">$k\gets 1, 2, \ldots, n$</span> do:</li>
<li><span class="math-container">$~~~$</span> if the max bin size used by <span class="math-container">$A(S, k)$</span> is at most 1:</li>
<li><span class="math-container">$~~~~~~$</span> return the packing of <span class="math-container">$S$</span> into <span class="math-container">$k$</span> bins achieved by <span class="math-container">$A(S, k)$</span></li>
<li>return the trivial packing of the <span class="math-container">$n$</span> items into <span class="math-container">$n$</span> bins</li>
</ol>
<hr />
<p>Next we verify that <span class="math-container">$B(S)$</span> returns a packing
of size at most OPT<span class="math-container">${}+O(f($</span>OPT<span class="math-container">$)). $</span></p>
<ol>
<li><p>Let <span class="math-container">$k^* = \min \{k : k-f(k) \ge {}$</span>OPT<span class="math-container">$\}.$</span></p>
</li>
<li><p>It is possible to pack <span class="math-container">$S$</span> into OPT bins of size 1.
That is, MinMax<span class="math-container">$(S, \,$</span>OPT<span class="math-container">$) {} \le 1$</span>.</p>
</li>
<li><p>So MinMax<span class="math-container">$(S, k^* - f(k^*)) \le 1$</span>.</p>
</li>
<li><p>So <span class="math-container">$A(S, k^*)$</span> can pack <span class="math-container">$S$</span> into <span class="math-container">$k^*$</span> bins of size at most 1.</p>
</li>
<li><p>So <span class="math-container">$B(S)$</span> packs <span class="math-container">$S$</span> into at most <span class="math-container">$k^*$</span> bins of size 1.
(Note this holds even if <span class="math-container">$k^* &gt; n$</span>.)</p>
</li>
<li><p>The choice of <span class="math-container">$k^*$</span> gives <span class="math-container">$k^* &lt; {}$</span>OPT<span class="math-container">${} + f(k^* - 1) + 1
= {}$</span>OPT<span class="math-container">${} + O(f($</span>OPT<span class="math-container">$))$</span>.</p>
</li>
</ol>
<p>The equality in the last step uses that <span class="math-container">$f(k)$</span> is sublinear.
This shows the &quot;only if&quot; direction.</p>
<hr />
<p>Next we show the &quot;if&quot; direction.
Assume there is a poly-time algorithm for Bin Packing that guarantees to pack <span class="math-container">$S$</span> into at most OPT+<span class="math-container">$f($</span>OPT<span class="math-container">$)$</span> size-1 bins.</p>
<p>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 <span class="math-container">$s$</span> is given,
and the problem is to pack the given numbers into a minimum number
of bins of size <span class="math-container">$s$</span>.
(This is without loss of generality:
in polynomial time,
we can take <span class="math-container">$s$</span> to be the product of the denominators of the given numbers, and scale every given number by <span class="math-container">$s$</span>.)
Let <span class="math-container">$B(S, s)$</span> denote the assumed Bin Packing algorithm,
modified to take inputs in this form.</p>
<p>Likewise, assume in OP's problem that the given numbers are integers. (This is WLOG as OP's problem is invariant under scaling.)</p>
<p>Given an instance <span class="math-container">$(S=(a_1,\ldots, a_n), k)$</span> of OP's problem
(where <span class="math-container">$S\subset \mathbb N$</span>),
the algorithm will use binary search
to find the minimum integer <span class="math-container">$s'$</span> such that
<span class="math-container">$B(S, s')$</span> packs <span class="math-container">$S$</span> into at most <span class="math-container">$k$</span> bins of size <span class="math-container">$s'$</span>.
It then returns that packing.
The binary search is on integers in the range <span class="math-container">$[1, U],$</span>
where <span class="math-container">$U=\sum_{i=1}^n a_i$</span>
(so all items can be packed into one bin of size <span class="math-container">$U$</span>).
This specifies the algorithm.</p>
<p>The binary search requires <span class="math-container">$O(\log U)$</span> iterations.
This is polynomial in the size of the input
(in particular, in the number of bits needed to encode
all <span class="math-container">$n$</span> numbers in <span class="math-container">$S$</span>).
So the algorithm takes polynomial time.</p>
<hr />
<p>To finish we verify that this <span class="math-container">$s'$</span> is at most MaxMin<span class="math-container">$(S, k - f(k))$</span>.</p>
<ol>
<li><p>Let OPT be the minimum number of size-<span class="math-container">$(s'-1)$</span> bins needed to pack <span class="math-container">$S$</span>.</p>
</li>
<li><p>We need to show that MaxMin<span class="math-container">$(S, k - f(k)) \ge s'$</span>.</p>
</li>
<li><p>Note that this is equivalent to OPT<span class="math-container">$ {} &gt; k - f(k).$</span></p>
</li>
<li><p>If OPT<span class="math-container">${} &gt; k$</span>, we are done, so assume OPT<span class="math-container">${}\le k.$</span></p>
</li>
<li><p><span class="math-container">$B$</span>'s guarantee and the choice of <span class="math-container">$s'$</span> imply OPT<span class="math-container">${}+f($</span>OPT<span class="math-container">$) {} &gt; k$</span>, i.e. OPT<span class="math-container">${} &gt; k - f($</span>OPT<span class="math-container">$).$</span></p>
</li>
<li><p><span class="math-container">$f$</span> is non-decreasing and OPT <span class="math-container">${} \le k$</span>, so this implies
OPT<span class="math-container">${} &gt; k - f(k)$</span>, as desired.</p>
</li>
<li><p>Per Step 3 above, this completes the proof. <span class="math-container">$~~~\Box$</span>.</p>
</li>
</ol>

CC BY-SA 4.0
2024-03-30T21:43:37.097Z
2024-03-31T13:28:55.657Z
2024-03-31T13:28:55.657Z
Neal Young
<p>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:</p>
<ol>
<li>The largest sum is at most <span class="math-container">$\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$</span>;</li>
<li>The smallest sum is at least <span class="math-container">$\operatorname{MaxMin}(S, 2k-1)$</span>.</li>
</ol>
<p><em>Proof.</em> Let <span class="math-container">$X_1,\ldots,X_k$</span> be the outcome of the greedy algorithm. It is sufficient to prove the claims for an arbitrary subset from this partition, say for <span class="math-container">$X_1$</span>. For any set <span class="math-container">$X$</span>, denote by <span class="math-container">$v(X)$</span> the sum of numbers in <span class="math-container">$X$</span>.</p>
<p><em>Proof of 1.</em>
Let  <span class="math-container">$Z_1,\ldots,Z_{\lfloor(k+1)/2\rfloor}$</span> be a min-max partition.
If <span class="math-container">$X_1$</span> contains a single item, then it is contained in at least one <span class="math-container">$Z_i$</span>, so <span class="math-container">$v(X_1)\leq \max_i v(Z_i)$</span>.
Otherwise, let <span class="math-container">$x_1$</span> be the last item added to <span class="math-container">$X_1$</span>. By the greedy algorithm definition, both <span class="math-container">$v(x_1)$</span> and <span class="math-container">$v(X_1\setminus \{x_1\})$</span> are smaller than <span class="math-container">$v(X_2),\ldots,v(X_k)$</span>. So in the <span class="math-container">$(k+1)$</span>-partition <span class="math-container">$\{x_1\},X_1\setminus \{x_1\},X_2,\ldots,X_k$</span>, the first two elements are smallest. Therefore, their sum is at most <span class="math-container">$2/(k+1)$</span> of the total:
<span class="math-container">\begin{align*}
v(X_1) \leq \frac{2}{k+1}v(S)
\end{align*}</span>
On the other hand:
<span class="math-container">\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*}</span>
Therefore, <span class="math-container">$v(X_1)\leq \max_i v(Z_i)$</span> too.</p>
<p><em>Proof of 2.</em>
Let <span class="math-container">$x_2,\ldots,x_k$</span> be the last item added to <span class="math-container">$X_2,\ldots,X_k$</span> respectively.
By the greedy algorithm definition, if we remove <span class="math-container">$x_2,\ldots,x_k$</span> from <span class="math-container">$X_2,\ldots,X_k$</span>, then <span class="math-container">$v(X_1)$</span> is largest among the remaining subsets. Therefore,
<span class="math-container">\begin{align*}
v(X_1)\geq \frac{1}{k}v(S\setminus \{x_2,\ldots,x_k\})
\end{align*}</span></p>
<p>Let <span class="math-container">$Y_1,\ldots, Y_{2k-1}$</span> be an optimal <span class="math-container">$(2k-1)$</span> partition.
The items <span class="math-container">$x_i$</span> belong to at most <span class="math-container">$n-1$</span> sets in the partition <span class="math-container">$Y$</span>, so there are at last <span class="math-container">$n$</span> sets in that partition that do not contain any <span class="math-container">$x_i$</span>; denote them by <span class="math-container">$Y_1,\ldots,Y_k$</span>. So
<span class="math-container">\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*}</span>
Therefore, <span class="math-container">$v(X_1)\geq \min_i v(Y_i)$</span>.</p>
<p>So the greedy algorithm is a 2-approximation. The question of whether there exists an additive approximation remains open.</p>

CC BY-SA 4.0
2020-11-24T13:01:02.863Z
Is this bound tight for the algorithm?
Neal Young
CC BY-SA 4.0
2020-11-24T17:47:26.763Z
@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
CC BY-SA 4.0
2020-11-24T11:35:00.890Z
2020-11-24T11:35:00.890Z
Erel Segal-Halevi
<p>The <span class="math-container">$k$</span>-way number partitioning problem accepts as input a multiset <span class="math-container">$S$</span> of positive numbers, and returns a partition of <span class="math-container">$S$</span> into <span class="math-container">$k$</span> subsets such that the subset sums are as nearly-equal as possible, namely,</p>
<ul>
<li>the largest sum is as small as possible, or -</li>
<li>the smallest sum is as large as possible.</li>
</ul>
<p>Both problems are NP-hard even for <span class="math-container">$k=2$</span>. Denote the optimal solutions of both problems by <span class="math-container">$MinMax(S,k)$</span> and <span class="math-container">$MaxMin(S,k)$</span> respectively. Note that both are weakly-decreasing functions of <span class="math-container">$k$</span>. Are there polynomial-time algorithms that find a partition of <span class="math-container">$S$</span> into <span class="math-container">$k$</span> subsets such that -</p>
<ul>
<li>the largest sum is at most <span class="math-container">$MinMax(S,k-1)$</span>, or -</li>
<li>the smallest sum is at least <span class="math-container">$MaxMin(S,k+1)$</span>?</li>
</ul>
<hr />
<p>The <a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning" rel="nofollow noreferrer">Wikipedia page on number partitioning</a> describes many polynomial-time approximation algorithms for this problem, but they have guarantees of different forms -  at most <span class="math-container">$(1+\epsilon)\cdot MinMax(S,k)$</span> or at least <span class="math-container">$(1-\epsilon)\cdot MaxMin(S,k)$</span>.</p>
<p>There are also algorithms that give constant-factor approximations to the related problems of <a href="https://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">bin packing</a> and <a href="https://en.wikipedia.org/wiki/Bin_covering_problem" rel="nofollow noreferrer">bin covering</a>. 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 <span class="math-container">$MinMax(S,k/(1+\epsilon))$</span> or <span class="math-container">$MaxMin(S,k/(1-\epsilon))$</span>, where <span class="math-container">$\epsilon$</span> is the corresponding approximation factor.</p>
<p>is it possible to attain in polynomial time, an additive <span class="math-container">$k$</span>-approximation?</p>

CC BY-SA 4.0
2020-11-22T16:37:53.533Z
I don't understand what you mean by additive k-approximation.
Chandra Chekuri
CC BY-SA 4.0
2020-11-23T11:25:51.403Z
@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
CC BY-SA 4.0
2020-11-23T23:33:48.100Z
The nomenclature "additive $k$-approximation" for what you want is not standard and is not clear.
Chandra Chekuri
CC BY-SA 4.0
2020-11-23T23:36:35.620Z
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. https://arxiv.org/abs/1301.4010
Chandra Chekuri
CC BY-SA 4.0
2020-11-24T02:26:39.383Z
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
CC BY-SA 4.0
2020-11-24T05:23:53.827Z
@NealYoung Greedy can be bad. Consider an instance with $k$ items  of size $1/2$ each $3k/2$ items of size $1/3$ each (assume  $k$ is even).
Chandra Chekuri
CC BY-SA 4.0
2020-11-24T11:36:14.033Z
@NealYoung I think the greedy algorithm guarantees at most $\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$ -- see the answer I just added. In particular, for $k=3$ it indeed guarantees $\operatorname{MinMax}(S, 2)$ , but in general it is only a 2-approximation.
Erel Segal-Halevi
CC BY-SA 4.0
2020-11-24T13:12:45.597Z
@ChandraChekuri For your example, isn't it the case that $\text{MinMax}(S, k-1)=7/6$?  The total weight is $k$, so one of the $k-1$ bins has to have weight more than 1, which means weight at least 7/6 as all weights are multiples of 1/6.  And doesn't the greedy algorithm (using $k$ bins) give max bin weight $7/6$?  You probably have in mind taking $k-1$ items of weight $1/2$ each and $3(k-1)/2$ items of size 1/3 each?  Then there is a packing into $k-1$ bins with max bin-weight 1, but greedy with $k$ bins gives max bin-weight $7/6$.
Neal Young
CC BY-SA 4.0
2020-11-24T20:07:40.727Z
I was only pointing out that Greedy won't give an additive  approx as the op wanted.
Chandra Chekuri
CC BY-SA 4.0
2020-11-25T01:49:46.047Z
@ChandraChekuri, right but for your example to demonstrate that for a given $k$, don't you need to replace $k$ by $k-1$ in your construction?  (This is a minor technical point.)
Neal Young
<approximation-algorithms><partition-problem>
A k-approximation to k-way number partitioning
Erel Segal-Halevi
# A k-approximation to k-way number partitioning

(Asked by: username_0 on 2020-11-21)

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](https://en.wikipedia.org/wiki/Multiway_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](https://en.wikipedia.org/wiki/Bin_packing_problem) and [bin covering](https://en.wikipedia.org/wiki/Bin_covering_problem). 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?

**Tags:** approximation-algorithms, partition-problem
> **Comments:**
> **username_1**: I don't understand what you mean by additive k-approximation.  
> **username_0**: @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?  
> **username_1**: The nomenclature "additive $k$-approximation" for what you want is not standard and is not clear.  
> **username_1**: 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. https://arxiv.org/abs/1301.4010  
> **username_2**: 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)$.  
> **username_1**: @NealYoung Greedy can be bad. Consider an instance with $k$ items  of size $1/2$ each $3k/2$ items of size $1/3$ each (assume  $k$ is even).  
> **username_0**: @NealYoung I think the greedy algorithm guarantees at most $\operatorname{MinMax}(S, \lfloor(k+1)/2\rfloor)$ -- see the answer I just added. In particular, for $k=3$ it indeed guarantees $\operatorname{MinMax}(S, 2)$ , but in general it is only a 2-approximation.  
> **username_2**: @ChandraChekuri For your example, isn't it the case that $\text{MinMax}(S, k-1)=7/6$?  The total weight is $k$, so one of the $k-1$ bins has to have weight more than 1, which means weight at least 7/6 as all weights are multiples of 1/6.  And doesn't the greedy algorithm (using $k$ bins) give max bin weight $7/6$?  You probably have in mind taking $k-1$ items of weight $1/2$ each and $3(k-1)/2$ items of size 1/3 each?  Then there is a packing into $k-1$ bins with max bin-weight 1, but greedy with $k$ bins gives max bin-weight $7/6$.  
> **username_1**: I was only pointing out that Greedy won't give an additive  approx as the op wanted.  
> **username_2**: @ChandraChekuri, right but for your example to demonstrate that for a given $k$, don't you need to replace $k$ by $k-1$ in your construction?  (This is a minor technical point.)  

---

## 2 answers

### Answer by username_2 on 2024-03-30. Score: 2 | Accepted answer

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](https://en.wikipedia.org/wiki/Bin_packing_problem#Additive_approximation)
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](https://cstheory.stackexchange.com/questions/50995/is-logarithmic-additive-approximation-to-bin-covering-possible) 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$.


---

### Answer by username_0 on 2020-11-24. Score: 0

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.

> **Comments:**
> **username_2**: Is this bound tight for the algorithm?  
> **username_0**: @NealYoung good question. I tried to find an example for tightness but failed. Perhaps the greedy algorithm attains better than 2-approximation.  

---

