An Online Algorithm for Maximizing Submodular Functions

By Matthew J. Streeter, D. Golovin. Neural Information Processing Systems, 2008

296 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/7528e41f8075d646b1e334fdc77c867cbea48549

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Submodular Maximization with Cardinality Constraints (2014, background): “Image segmentation [6, 30] and speeding up satisfiability solvers [49] are additional examples in which submodular maximization is useful.”
Learning diverse rankings with multi-armed bandits (2008, methodology): “A generalization of this algorithm, in an abstract setting without the application to Information Retrieval, was discovered independently by Streeter and Golovin (2007).”
Scalable influence maximization for prevalent viral marketing in large-scale social networks (2010, methodology): “The proof of this result is included in [3], which is adapted from the original proof in [19].”
Introduction to Multi-Armed Bandits (2019, background): “rrespond to rankings of items such as search results, a user scrolls down to the ﬁrst “relevant” item, clicks on it, and leaves. The study of this model has been initiated in Radlinski et al. (2008); Streeter and Golovin (2008), with further developments in Kveton et al. (e.g., 2015b,a); Zong et al.”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, methodology): “Kveton et al. (2014) studies linear matroid bandits, which is a subclass of the linear combinatorial bandits we discussed in Section 4.2, and they provide better regret bounds than our general bounds given in Section 4.2, because their analysis utilizes the matroid combinatorial structure.”
SpeedBoost: Anytime Prediction with Uniform Near-Optimality (2012, methodology): “Following the same structure as the analysis in [14], we can now prove that the set selected by the greedy algorithm approximates the optimal sequence of elements for functions which satisfy Definition 5.”
Submodular Function Maximization (2014, background): “Streeter and Golovin (2007) also provide results for other feedback models showing it is possible to obtain expected average (1 − 1 /e )-regret which converges to zero as T → ∞ , up to and including the bandit feedback model in which only the reward of the set selected, namely r t S ( t ) i − 1 ,…”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “This can be done both for the maximization of submodular functions [198, 88] or their minimization [93] – Learning submodular functions: We have assumed that the set-functions we were working with were given, and hence manually built for each given application.”
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2010, methodology): “If f is adaptive monotone and adaptive submodular with respect to the distribution P [Φ], π is an α-approximate greedy policy with respect to the item costs, and π∗ is any policy, then cΣ(π) ≤ 4α cΣ(π∗).”
Contextual Sequence Prediction with Application to Control Library Optimization (2012, methodology): “[24] over hypothesis space of predictors which is guaranteed to yield sequences within a constant factor of the optimal sequence.”
Cascading Bandits: Learning to Rank in the Cascade Model (2015, background): “This setting is common in the problems of our interest, such as web search.”