nips nips2008 nips2008-22 nips2008-22-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthew Streeter, Daniel Golovin
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. 1
[1] Noga Alon, Baruch Awerbuch, and Yossi Azar. The online set cover problem. In Proceedings of the 35th STOC, pages 100–105, 2003.
[2] Peter Auer, Nicol` Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic o multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002.
[3] Shivnath Babu, Rajeev Motwani, Kamesh Munagala, Itaru Nishizawa, and Jennifer Widom. Adaptive ordering of pipelined stream filters. In Proc. Intl. Conf. on Management of Data, pages 407–418, 2004.
[4] Nicol` Cesa-Bianchi, Yoav Freund, David Haussler, David Helmbold, Robert Schapire, and o Manfred Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, 1997.
[5] Edith Cohen, Amos Fiat, and Haim Kaplan. Efficient sequences of trials. In Proceedings of the 14th SODA, pages 737–746, 2003.
[6] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634– 652, 1998.
[7] Uriel Feige, L´ szl´ Lov´ sz, and Prasad Tetali. Approximating min sum set cover. Algoritha o a mica, 40(4):219–234, 2004.
[8] Carla P. Gomes and Bart Selman. Algorithm portfolios. Artificial Intelligence, 126:43–62, 2001.
[9] Bernardo A. Huberman, Rajan M. Lukose, and Tad Hogg. An economics approach to hard computational problems. Science, 275:51–54, 1997.
[10] Sham Kakade, Adam Kalai, and Katrina Ligett. Playing games with approximation algorithms. In Proceedings of the 39th STOC, pages 546–555, 2007.
[11] Haim Kaplan, Eyal Kushilevitz, and Yishay Mansour. Learning with attribute costs. In Proceedings of the 37th STOC, pages 356–365, 2005.
[12] Samir Khuller, Anna Moss, and Joseph (Seffi) Naor. The budgeted maximum coverage problem. Information Processing Letters, 70(1):39–45, 1999.
[13] Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the 21st UAI, pages 324–331, 2005.
[14] Andreas Krause and Carlos Guestrin. A note on the budgeted maximization of submodular functions. Technical Report CMU-CALD-05-103, Carnegie Mellon University, 2005.
[15] Kamesh Munagala, Shivnath Babu, Rajeev Motwani, Jennifer Widom, and Eiter Thomas. The pipelined set cover problem. In Proc. Intl. Conf. on Database Theory, pages 83–98, 2005.
[16] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265–294, 1978.
[17] Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th ICML, pages 784–791, 2008.
[18] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Technical Report CMU-CS-07-171, Carnegie Mellon University, 2007.
[19] Matthew Streeter, Daniel Golovin, and Stephen F. Smith. Combining multiple heuristics online. In Proceedings of the 22nd AAAI, pages 1197–1203, 2007.
[20] Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32:41–43, 2004. 8