An Online Algorithm for Maximizing Submodular Functions

Keywords

Submodular set function, Algorithm, Computer science, Mathematical optimization, Mathematics

References

• Restart Schedules for Ensembles of Problem InstancesM. J. V. Streeter, Daniel Golovin, Stephen F. Smith — 2007
• Greedy algorithms for on-line set-covering and related problemsGiorgio Ausiello, Aristotelis Giannakos, Vangélis Th. Paschos — 2006
• A Note on the Budgeted Maximization of Submodular FunctionsAndreas Krause, Carlos Guestrin — 2005
• An analysis of approximations for maximizing submodular set functions—IGeorge L. Nemhauser, Laurence A. Wolsey, Marshall L. Fisher — 1978
• A threshold of ln n for approximating set cover (preliminary version)Uriel Feige — 1996
• Concentration Inequalities and Martingale Inequalities: A SurveyFan Chung, Linyuan Lü — 2006
• Efficient sequences of trialsEdith Cohen, Amos Fiat, Haim Kaplan — 2003
• Adaptive routing with end-to-end feedback: distributed learning and geometric approachesBaruch Awerbuch, Robert Kleinberg — 2004
• Learning diverse rankings with multi-armed banditsFilip Radlinski, Robert Kleinberg, Thorsten Joachims — 2008
• Learning with attribute costsHaim Kaplan, Eyal Kushilevitz, Yishay Mansour — 2005
• A note on maximizing a submodular set function subject to a knapsack constraintMaxim Sviridenko — 2004
• How to use expert adviceNicolò Cesa‐Bianchi, Yoav Freund, David P. Helmbold — 1993
• The weighted majority algorithmN. Littlestone, Manfred K. Warmuth — 1989
• Playing games with approximation algorithmsSham M. Kakade, Adam Tauman Kalai, Katrina Ligett — 2007
• Maximizing the spread of influence through a social networkDavid Kempe, Jon Kleinberg, Éva Tardos — 2003
• An Economics Approach to Hard Computational ProblemsBernardo A. Huberman, Rajan M. Lukose, Tad Hogg — 1997
• The Nonstochastic Multiarmed Bandit ProblemPeter Auer, Nicolò Cesa‐Bianchi, Yoav Freund — 2002
• The Budgeted Maximum Coverage ProblemSamir Khuller, Anna Moss, Joseph Naor — 1999
• Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction ProblemsCarla P. Gomes, Bart Selman, Nuno Crato — 2000
• Adaptive ordering of pipelined stream filtersShivnath Babu, Rajeev Motwani, Kamesh Munagala — 2004

Cited by

• Online Learning Techniques for Improving Robot Navigation in Unfamiliar DomainsBoris Sofman — 2010
• Selective Data Gathering in Community Sensor NetworksMatthew Nicholas Faulkner — 2014
• Online submodular minimizationElad Hazan, Satyen Kale — 2009
• Interactive Learning for Sequential Decisions and PredictionsStéphane Ross — 2013
• Anytime Prediction: Efficient Ensemble Methods for Any Computational BudgetAlexander Grubb — 2014
• Efficient Optimization of Control LibrariesDebadeepta Dey, Tian Yu Liu, Boris Sofman — 2011
• Online algorithms for submodular minimization with combinatorial constraintsStefanie Jegelka, Jeffrey A. Bilmes — 2010
• Emergency maneuver library - ensuring safe navigation in partially known environmentsSankalp Arora, Sanjiban Choudhury, Daniel Althoff — 2015
• Predicting Contextual Sequences via Submodular Function MaximizationDebadeepta Dey, Tian Yu Liu, Martial Hebert — 2012
• Learning to rank from implicit feedbackFilip Radlinski — 2008
• On the complexity of information planning in Gaussian modelsGeorgios Papachristoudis, John W. Fisher — 2015
• Online Learning of Assignments that Maximize Submodular FunctionsDaniel Golovin, Andreas Krause, M. J. V. Streeter — 2009
• Approximation Algorithms for Bayesian Multi-Armed Bandit ProblemsSudipto Guha, Kamesh Munagala — 2013
• Interactive Submodular Set CoverAndrew Guillory, Jeff Bilmes — 2010
• Contextual Sequence Prediction with Application to Control Library OptimizationDebadeepta Dey, Tian Yu Liu, Martial Hebert — 2012
• Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document SummarizationJiaji Zhou, Stéphane Ross, Yisong Yue — 2013
• Dynamic Resource Allocation in Conservation PlanningDaniel Golovin, Andreas Krause, Beth Gardner — 2011
• Towards open ended learning: budgets, model selection, and representationPietro Perona, Ryan G. Gomes — 2011
• Submodularity in Batch Active Learning and Survey Problems on Gaussian Random FieldsYifei Ma, Roman Garnett, Jeff Schneider — 2012
• Cascading Bandits: Learning to Rank in the Cascade ModelBranislav Kveton, Csaba Szepesvári, Zheng Wen — 2015

Related papers

• Lower bounds on the independence number of certain graphs of odd girth at least sevenAnders Sune Pedersen, Dieter Rautenbach, Friedrich Regen — 2011
• Independent transversals in bipartite correspondence-coversStijn Cambie, Ross J. Kang — 2020
• Up-embeddability of graphs with small orderShengxiang Lv, Yanpei Liu — 2010
• Minimal Estrada index of the trees without perfect matchingsWenhuan Wang, Chun-Xiang Zhai — 2019
• Leveraging semantic saliency maps for query-specific video summarizationKemal Cizmeciler, Erkut Erdem, Aykut Erdem — 2022
• Non-Monotone Adaptive Submodular MaximizationAlkis Gotovos, Amin Karbasi, Andreas Krause — 2015
• Robust Budget Allocation Via Continuous Submodular FunctionsMatthew Staib, Stefanie Jegelka — 2017
• Risk-Aware Submodular Optimization for Multirobot CoordinationLifeng Zhou, Pratap Tokekar — 2020