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".