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.