An approximation scheme for minimizing agreeably weighted variance on a single machine

An approximation scheme for minimizing agreeably weighted variance on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20002779
Country: United States
Volume: 11
Issue: 2
Start Page Number: 211
End Page Number: 216
Publication Date: Mar 1999
Journal: INFORMS Journal On Computing
Authors:
Abstract:

We consider the problem of minimizing the weighted variance of job completion times on a single machine with job-dependent, agreeable weights. In 1995, Cai derived a fully polynomial time approximation scheme for the special case where the weights of the jobs are polynomially bounded in the number n of jobs. In this article, we completely settle the approximability status of this scheduling problem. We construct a fully polynomial time approximation scheme for the general case, without putting any restrictions on the weights of the jobs.

Reviews

Required fields are marked *. Your email address will not be published.