Timezone: »
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)
-
2008 Poster: An Online Algorithm for Maximizing Submodular Functions »
Wed. Dec 10th through Tue the 9th Room
More from the Same Authors
-
2012 Poster: No-Regret Algorithms for Unconstrained Online Convex Optimization »
Matthew Streeter · Brendan McMahan -
2010 Poster: Near-Optimal Bayesian Active Learning with Noisy Observations »
Daniel Golovin · Andreas Krause · Debajyoti Ray -
2009 Poster: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2009 Spotlight: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause