CMU-CS-07-171Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-07-171
Matthew Streeter, Daniel Golovin December 2007
CMU-CS-07-171.ps
Keywords: Online Algorithms, submodular functions
We consider the following two problems. We are given as input a set of
activities and a set of jobs to complete. Our goal is to devise a
schedule for allocating time to the various activities so as to achieve
one of two objectives: minimizing the average time required to complete
each job, or maximizing the number of jobs completed within a fixed time
(v,t) represents investing
time t in activity v. We assume that
the fraction of jobs completed, f, is a monotone submodular function of
the sequence of pairs that appear in a schedule.
In the offline setting in which we have oracle access to We consider these problems in the online setting, in which the jobs arrive one at a time and we must finish each job (via some schedule) before moving on to the next. We give an efficient online algorithm for this problem whose worst-case asymptotic performance is simultaneously optimal for both objectives (unless P = NP), in the sense that its performance ratio (with respect to the optimal static schedule) converges to the best approximation ratios for the corresponding offline problems. Finally, we evaluate this algorithm experimentally by using it to learn, online, a schedule for allocating CPU time to the solvers entered in the 2007 SAT solver competition. 39 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |