Multifit algorithm

The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of multiprocessor scheduling with identical processors. It was developed by Coffman, Garey and Johnson. 
The algorithm.
The input to the algorithm is a set "S" of numbers, and a parameter "k". The required output is a partition of "S" into "k" subsets, such that the largest subset sum (also called the makespan) in as small as possible.
The algorithm performs a binary search to find the minimum bin capacity for which a certain algorithm for the bin packing problem finds a feasible solution.
Analysis.
Multifit is a constant-factor approximation algorithm. It always finds a partition in which the makespan is at most a constant factor larger than the optimal makespan. The constant factor for small values of "k" is:
For general "k", it was proved that the upper bound is 1.220. It was later improved to 6/5=1.2, and later to 13/11≈1.182. This is almost tight: there is an instance with "k"=13 in which the approximation ratio is exactly 13/11.