An Online Algorithm for Maximizing Submodular Functions

Citations Over Time

Abstract

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, τ), where τ 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.

Related Papers

• → Leveraging semantic saliency maps for query-specific video summarization(2022)21 cited
• → Independent transversals in bipartite correspondence-covers(2021)9 cited
• → Lower bounds on the independence number of certain graphs of odd girth at least seven(2010)5 cited
• → Up-embeddability of graphs with small order(2009)1 cited
• → Minimal Estrada index of the trees without perfect matchings(2019)