Scheduling with Outliers

DOI10.1007/978-3-642-03685-9_12zbMATH Open1255.90060arXiv0906.2020OpenAlexW2076515080MaRDI QIDQ3638875FDOQ3638875

Authors: Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Danny Segev 

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0906.2020

Recommendations

• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling jobs that arrive over time
• scientific article; zbMATH DE number 871909
• Single machine scheduling with release dates
• Scheduling-LPs bear probabilities. Randomized approximations for min-sum criteria

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cited In (9)

• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• New approximation results for resource replication problems
• Min sum clustering with penalties
• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
• Minimizing average flow-time under knapsack constraint
• A primal-dual approximation algorithm for min-sum single-machine scheduling problems
• A primal-dual approximation algorithm for Min-sum single-machine scheduling problems
• Rejecting jobs to minimize load and maximum flow-time
• On the fine-grained parameterized complexity of partial scheduling to minimize the makespan

This page was built for publication: Scheduling with Outliers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638875)