Computer Science Department
School of Computer Science, Carnegie Mellon University


An Online Algorithms for Maximizing
Submodular Functions

Matthew Streeter, Daniel Golovin

December 2007

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 T. Formally, a schedule is a sequence <(v1,t1), (v2,t2), ...>, where each pair (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 f, these two objectives give us, respectively, what we call the Min Sum Submodular Cover problem (which is a generalization of the Min Sum Set Cover problem and the related Pipelined Set Cover problem) and what we call Budgeted Maximum Submodular Coverage (which generalizes the problem of maximizing a monotone, submodular function subject to a knapsack constraint).

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
School of Computer Science

This page maintained by