## Abstract

We consider the classic scheduling/load balancing problems where there are m identical machines and n jobs, and each job should be assigned to some machine. Traditionally, the assignment of jobs to machines is measured by the makespan (maximum load) i.e., the L_{∞} norm of the assignment. An ε-approximation scheme was given by Hochbaum and Shmoys for minimizing the L_{∞} norm. In several applications, such as in storage allocation, a more appropriate measure is the sum of the squares of the loads (which is equivalent to the L_{2} norm). This problem was considered in [4, 5, 13] who showed how to approximate the optimum value by a factor of about 1.04. In fact, a more general measure, which is the L_{p} norm (for any p≥1) can also be approximated to some constant which may be as large as 3/2. We improve these results by providing an ε-approximation scheme for the general L_{p} norm (and in particular for the L_{2} norm). We also consider the case of restricted assignment of unit jobs where we show how to find in polynomial time, a solution which is optimal for all norms.

Original language | English (US) |
---|---|

Pages | 493-500 |

Number of pages | 8 |

State | Published - Jan 1 1997 |

Externally published | Yes |

Event | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997 |

### Other

Other | Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | New Orleans, LA, USA |

Period | 1/5/97 → 1/7/97 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)