Timezone: »

An Online Algorithm for Maximizing Submodular Functions
Matthew Streeter · Daniel Golovin

Tue Dec 09 07:30 PM -- 12:00 AM (PST) @

We present an algorithm for solving a broad class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities, according to some schedule. We assume that the fraction of jobs completed by a schedule is a monotone, submodular function of a set of pairs (v,t), where t is the time invested in activity v. Under this assumption, our online algorithm performs near-optimally according to two natural metrics: (i) the fraction of jobs completed within time T, for some fixed deadline T > 0, and (ii) the average time required to complete each job. We evaluate our algorithm experimentally by using it to learn, online, a schedule for allocating CPU time among solvers entered in the 2007 SAT solver competition.

Author Information

Matthew Streeter (Duolingo)
Daniel Golovin (Google, Inc)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors