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?