Scheduling with Outliers Export

@article{citeulike:5038059, abstract = {In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer required to process all jobs -- we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still approximately minimizing the objective function? We refer to this class of problems as scheduling with outliers. This model was initiated by Charikar and Khuller (SODA'06) on the minimum max-response time in broadcast scheduling. We consider three other well-studied scheduling objectives: the generalized assignment problem, average weighted completion time, and average flow time, and provide LP-based approximation algorithms for them. For the minimum average flow time problem on identical machines, we give a logarithmic approximation algorithm for the case of unit profits based on rounding an LP relaxation; we also show a matching integrality gap. For the average weighted completion time problem on unrelated machines, we give a constant factor approximation. The algorithm is based on randomized rounding of the time-indexed LP relaxation strengthened by the knapsack-cover inequalities. For the generalized assignment problem with outliers, we give a simple reduction to GAP without outliers to obtain an algorithm whose makespan is within 3 times the optimum makespan, and whose cost is at most (1 + \epsilon) times the optimal cost.}, archivePrefix = {arXiv}, author = {Gupta, Anupam and Krishnaswamy, Ravishankar and Kumar, Amit and Segev, Danny}, citeulike-article-id = {5038059}, citeulike-linkout-0 = {http://arxiv.org/abs/0906.2020}, citeulike-linkout-1 = {http://arxiv.org/pdf/0906.2020}, comment = {Outliers read "optional".}, eprint = {0906.2020}, keywords = {approximation, optimization}, month = {Jun}, posted-at = {2009-07-02 01:23:25}, priority = {2}, title = {Scheduling with Outliers}, url = {http://arxiv.org/abs/0906.2020}, year = {2009} }

TY - JOUR ID - citeulike:5038059 L3 - citeulike-article-id:5038059 N2 - In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer required to process all jobs -- we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still approximately minimizing the objective function? We refer to this class of problems as scheduling with outliers. This model was initiated by Charikar and Khuller (SODA'06) on the minimum max-response time in broadcast scheduling. We consider three other well-studied scheduling objectives: the generalized assignment problem, average weighted completion time, and average flow time, and provide LP-based approximation algorithms for them. For the minimum average flow time problem on identical machines, we give a logarithmic approximation algorithm for the case of unit profits based on rounding an LP relaxation; we also show a matching integrality gap. For the average weighted completion time problem on unrelated machines, we give a constant factor approximation. The algorithm is based on randomized rounding of the time-indexed LP relaxation strengthened by the knapsack-cover inequalities. For the generalized assignment problem with outliers, we give a simple reduction to GAP without outliers to obtain an algorithm whose makespan is within 3 times the optimum makespan, and whose cost is at most (1 + \epsilon) times the optimal cost. TI - Scheduling with Outliers KW - approximation KW - optimization N1 - Outliers read "optional". AU - Gupta, Anupam AU - Krishnaswamy, Ravishankar AU - Kumar, Amit AU - Segev, Danny PY - 2009/Jun/10/ UR - http://arxiv.org/abs/0906.2020 ER -