5
$\begingroup$

The multiway number partitioning problem 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), 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)). 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".

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Jun 23 at 20:29
  • 1
    $\begingroup$ @NealYoung I have added an example. $\endgroup$
    – Erel Segal-Halevi
    Jun 25 at 12:31
  • $\begingroup$ I guess there is a typo: it should be $(1+\epsilon)\mathit{OPTMIN}$ and $(1-\epsilon)\mathit{OPTMAX}$. $\endgroup$
    – Heda Chen
    Jun 27 at 4:11
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erel Segal-Halevi
    Jun 27 at 15:02
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Jun 29 at 11:24

0

Reset to default

Your Answer

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