In the k-way number partitioning problem, the input is a set of numbers and the goal is to partition them into $k$ parts in an optimal way. The most well-studied optimization objective is to minimize the largest sum; this problem is equivalent to minimizing the makespan when scheduling jobs on $k$ identical machines. For this objective, there are practical constant-factor approximation algorithms, attaining 4/3 or 6/5 or 7/6 or 13/11 approximation.
I am interested in the dual objective - to maximize the smallest sum. For this objective, there is a PTAS - but it is considered impractical since the run-time is polynomial with a very high degree. There is also a constant-factor approximation, which attains an approximation factor of 3/4. My question is: are there practical algorithms that attain a better constant-factor approximation for the max-min objective? I am looking for something comparable to the min-max objective, e.g. 4/5 or 5/6 or 6/7 or 11/13.
