<p>The <a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning" rel="nofollow noreferrer">multiway number partitioning problem</a> has two optimization variants: in one variant the goal is to minimize the largest bin sum (the &quot;makespan&quot;), and in the other variant the goal is to maximxize the smallest bin sum. The optimal solutions for these variants may be different. For example <sub>(from <a href="https://link.springer.com/article/10.1007/s10100-011-0217-4" rel="nofollow noreferrer">this paper</a>)</sub>, for a three-way partitioning of <span class="math-container">$[46, 39, 27, 26, 16, 13, 10]$</span>:</p>
<ul>
<li>The min max partition is <span class="math-container">$[27, 26], [46, 16], [39, 13, 10]$</span> with sums <span class="math-container">$53, 62, 62$</span>; optimal max-sum is 62.</li>
<li>The max min partition is  <span class="math-container">$[46, 10], [27, 16, 13], [39, 26]$</span> with sums <span class="math-container">$56, 56, 65$</span>; the optimal min-sum is 56.</li>
</ul>
<p>For any fixed <span class="math-container">$n$</span> (number of bins), each variant has an FPTAS (see e.g. <a href="https://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901" rel="nofollow noreferrer">Woeginger (2000)</a>). Is there an FPTAS for both variants simultaneously? That is, an algorithm that, for every <span class="math-container">$\epsilon&gt;0$</span>, finds an <span class="math-container">$n$</span>-way partition of the input list, such that the smallest bin sum is at least <span class="math-container">$(1-\epsilon)\cdot OPTMIN$</span>, and the largest bin sum is at most <span class="math-container">$(1+\epsilon)\cdot OPTMAX$</span> (if such a partition exists), and runs in time polynomial in the problem size and <span class="math-container">$1/\epsilon$</span>.</p>
<p>For broader context, I will be happy to know if any other optimization problems admit such a &quot;simultaneous FPTAS&quot;.</p>

CC BY-SA 4.0
2023-06-23T20:29:02.133Z
For intuition, can you describe a simple instance that has no solution that simultaneously minimizes the max bin sum and maximizes the min bin sum?
Neal Young
CC BY-SA 4.0
2023-06-25T12:31:34.660Z
@NealYoung I have added an example.
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-27T04:11:11.710Z
I guess there is a typo: it should be $(1+\epsilon)\mathit{OPTMIN}$ and $(1-\epsilon)\mathit{OPTMAX}$.
Heda Chen
CC BY-SA 4.0
2023-06-27T15:02:34.560Z
@Marcythm OPTMIN is the optimal value of a maximization problem - maximize the minimum bin sum. So the approximation is $(1-\epsilon)\cdot OPTMIN$. Similarly, OPTMAX is the optimal value of a minimization problem. In the example, OPTMIN=56 and OPTMAX=62.
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-27T16:00:01.043Z
Oh sorry I corresponds them in a wrong way. You are right. Thank you for explanation.
Heda Chen
CC BY-SA 4.0
2023-06-29T11:24:04.890Z
Given that there are instances where the desired solution exists only if $\epsilon\ge c$ (for some small constant $c>0$), it seems likely to me that computing such a solution (with $\epsilon=c$, for some appropriate such instance) will be NP-hard.  Have you tried showing this?
Neal Young
<approximation-algorithms><partition-problem>
A simultaneous FPTAS for both max-min and min-max number partitioning
Erel Segal-Halevi
# A simultaneous FPTAS for both max-min and min-max number partitioning

(Asked by: username_0 on 2023-06-22)

The [multiway number partitioning problem](https://en.wikipedia.org/wiki/Multiway_number_partitioning) has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to maximxize the smallest bin sum. The optimal solutions for these variants may be different. For example (from [this paper](https://link.springer.com/article/10.1007/s10100-011-0217-4)), for a three-way partitioning of $[46, 39, 27, 26, 16, 13, 10]$:

* The min max partition is $[27, 26], [46, 16], [39, 13, 10]$ with sums $53, 62, 62$; optimal max-sum is 62.
* The max min partition is $[46, 10], [27, 16, 13], [39, 26]$ with sums $56, 56, 65$; the optimal min-sum is 56.

For any fixed $n$ (number of bins), each variant has an FPTAS (see e.g. [Woeginger (2000)](https://pubsonline.informs.org/doi/abs/10.1287/ijoc.12.1.57.11901)). Is there an FPTAS for both variants simultaneously? That is, an algorithm that, for every $\epsilon>0$, finds an $n$-way partition of the input list, such that the smallest bin sum is at least $(1-\epsilon)\cdot OPTMIN$, and the largest bin sum is at most $(1+\epsilon)\cdot OPTMAX$ (if such a partition exists), and runs in time polynomial in the problem size and $1/\epsilon$.

For broader context, I will be happy to know if any other optimization problems admit such a "simultaneous FPTAS".

**Tags:** approximation-algorithms, partition-problem

> **Comments:**
> **username_1**: For intuition, can you describe a simple instance that has no solution that simultaneously minimizes the max bin sum and maximizes the min bin sum?  
> **username_0**: @NealYoung I have added an example.  
> **username_2**: I guess there is a typo: it should be $(1+\epsilon)\mathit{OPTMIN}$ and $(1-\epsilon)\mathit{OPTMAX}$.  
> **username_0**: @Marcythm OPTMIN is the optimal value of a maximization problem - maximize the minimum bin sum. So the approximation is $(1-\epsilon)\cdot OPTMIN$. Similarly, OPTMAX is the optimal value of a minimization problem. In the example, OPTMIN=56 and OPTMAX=62.  
> **username_2**: Oh sorry I corresponds them in a wrong way. You are right. Thank you for explanation.  
> **username_1**: Given that there are instances where the desired solution exists only if $\epsilon\ge c$ (for some small constant $c>0$), it seems likely to me that computing such a solution (with $\epsilon=c$, for some appropriate such instance) will be NP-hard.  Have you tried showing this?  

---

## 0 answers

