An Online Algorithm for Maximizing Submodular Functions
Abstract
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. Formally, a schedule is a sequence where each pair represents investing time in an activity. We assume that the fraction of jobs completed is a monotone submodular function of the sequence of pairs that appear in a schedule. 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 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 20, 2007
- Accession Number
- ADA476871
Entities
People
- Daniel Golovin
- Matthew T. Streeter
Organizations
- Carnegie Mellon University