Thursday, March 11, 2010 - 16:30
1 hour (actually 50 minutes)
We look at problems of scheduling jobs to machines when the processing time of a job is machine dependent. Common objectives in this framework are to minimize the maximum load on a machine, or to minimize the average completion time of jobs. These are well-studied problems. We consider the related problem of trying to select a subset of machines to use to minimize machine costs subject to bounds on the maximum load or average completion time of the corresponding schedule. These problems are NP-hard and include set-cover as a special case. Thus we focus on approximation algorithms and get tight, or almost tight approximation guarantees. A key part of our results depends on showing the submodularity of the objective of a related optimization problem.