Speaker: Ravishankar Krishnaswamy

Title: Scheduling with Outliers

Abstract:
In classical scheduling problems, we are given jobs and machines, and have to 
schedule each and every job to minimize some objective function. In this talk, 
we consider situations where we are not required to process all jobs; rather, 
scheduling a ``profitable'' subset of jobs might be enough. In particular, we 
consider problems of scheduling with outliers: given an instance of some 
classical scheduling problem, imagine each job j also comes with a certain 
profit pi_j. Given a target profit Pi, the goal is now to pick a subset S of 
jobs whose total profit is at least Pi, and to schedule them to minimize the 
objective function of the underlying scheduling problem. We will describe 
LP-based approximation algorithms for three well-studied scheduling problems in 
the above model.