# Graham's 4/3-approximation for makespan on parallel machines,

or P||C_{max}

We are given *n* jobs. Each job *j* has a
processing
time *p*_{j}. We wish to find a schedule
for *m* parallel machines, which minimizes the maximal
completion time. This problem is unary NP-hard, but there is a polynomial time
approximation scheme (PTAS) but with high complexity,
and for a fixed number of machines even a fully polynomial time approximation scheme (FPTAS).
Algorithm by **Graham**:
Process jobs in order of decreasing processing times and
place them on the least charged machine.

## Input

## Output