Fetching the paper…
Reading the bibliography…
We consider the problem of maximizing a monotone submodular function under noise.
Cores of convex games
L. S. Shapley · 1971
Earlier work this paper cites.
Optimization of functions whose values are subject to small errors
Torkel Glad and Allen Goldstein · 1977
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions—II
Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey · 1978
Earlier work this paper cites.
Stochastic Approximation Methods for Constrained and Unconstrained Systems (Applied Mathematical Sciences, Vol. 26)
Harold J Kushner and Dean S Clark · 1978
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions—i
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher · 1978
Earlier work this paper cites.
Best algorithms for approximating the maximum of a submodular set function
George L Nemhauser and Leonard A Wolsey · 1978
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions—I
G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher · 1978
Earlier work this paper cites.
A Theory of the Learnable
Leslie G. Valiant · 1984
Earlier work this paper cites.
Introduction to optimization
Boris T Polyak · 1987
Earlier work this paper cites.
Queries and concept learning
Dana Angluin · 1988
Earlier work this paper cites.
Exact identification of circuits using fixed points of amplification functions (abstract)
Sally A. Goldman, Michael J. Kearns, and Robert E. Schapire · 1990
Earlier work this paper cites.
Computing with noisy information
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal · 1994
Earlier work this paper cites.
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
Jeffrey C. Jackson · 1994
Earlier work this paper cites.
A grid algorithm for bound constrained optimization of noisy functions
Clemens Elster and Arnold Neumaier · 1995
Earlier work this paper cites.
Learning by extended statistical queries and its relation to PAC learning
Eli Shamir and Clara Schwartzman · 1995
Earlier work this paper cites.
Response surfaces: designs and analyses
André I Khuri and John A Cornell · 1996
Earlier work this paper cites.
A threshold of ln n for approximating set cover
Uriel Feige · 1998
Earlier work this paper cites.
Learning with queries corrupted by classification noise
Jeffrey C. Jackson, Eli Shamir, and Clara Shwartzman · 1999
Earlier work this paper cites.
Combinatorial auctions with decreasing marginal utilities
Benny Lehmann, Daniel Lehmann, and Noam Nisan · 2001
Earlier work this paper cites.
On using extended statistical queries to avoid membership queries
Nader H. Bshouty and Vitaly Feldman · 2002
Earlier work this paper cites.
Maximizing the spread of influence through a social network
D. Kempe, J. Kleinberg, and E. Tardos · 2003
Earlier work this paper cites.
Pipage rounding: A new method of constructing algorithms with proven performance guarantee
Alexander A. Ageev and Maxim Sviridenko · 2004
Earlier work this paper cites.
Approximation algorithms for combinatorial auctions with complement-free bidders
Shahar Dobzinski, Noam Nisan, and Michael Schapira · 2005
Earlier work this paper cites.
Inapproximability results for combinatorial auctions with submodular utility functions
Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta · 2005
Earlier work this paper cites.
A note on the budgeted maximization of submodular functions
Andreas Krause and Carlos Guestrin · 2005
Earlier work this paper cites.
An improved approximation algorithm for combinatorial auctions with submodular bidders
Shahar Dobzinski and Michael Schapira · 2006
Earlier work this paper cites.
Approximation algorithms for allocation problems: Improving the factor of 1-1/e
Uriel Feige and Jan Vondrak · 2006
Earlier work this paper cites.
Maximizing a submodular set function subject to a matroid constraint
Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák · 2007
Earlier work this paper cites.
How to rank with few errors
Claire Kenyon-Mathieu and Warren Schudy · 2007
Earlier work this paper cites.
Nonmyopic active learning of gaussian processes. an exploration–exploitation approach
A. Krause and C. Guestrin · 2007
Earlier work this paper cites.
Selecting observations against adversarial objectives
Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Anupam Gupta · 2007
Earlier work this paper cites.
Cost-effective outbreak detection in networks
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance · 2007
Earlier work this paper cites.
The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)
Michael Ben Or and Avinatan Hassidim · 2008
Cited alongside, same era.
Noisy sorting without resampling
Mark Braverman and Elchanan Mossel · 2008
Cited alongside, same era.
Multi-unit auctions with budget limits
Shahar Dobzinski, Ron Lavi, and Noam Nisan · 2008
Cited alongside, same era.
Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies
Andreas Krause, Ajit Paul Singh, and Carlos Guestrin · 2008
Cited alongside, same era.
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions
Vahab S. Mirrokni, Michael Schapira, and Jan Vondrák · 2008
Cited alongside, same era.
On the hardness of being truthful
Christos H. Papadimitriou, Michael Schapira, and Yaron Singer · 2008
Optimal selection of limited vocabulary speech corpora
H. Lin and J. Bilmes · 2011
Later among the works it cites.
On optimal single-item auctions
Christos H. Papadimitriou and George Pierrakos · 2011
Later among the works it cites.
Inferring networks of diffusion and influence
M. Gomez Rodriguez, J. Leskovec, and A. Krause · 2011
Later among the works it cites.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Jan Vondrák, Chandra Chekuri, and Rico Zenklusen · 2011
Later among the works it cites.
Sketching valuation functions
Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden · 2012
Later among the works it cites.
Learning valuation functions
Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Inapproximability of combinatorial public projects
Michael Schapira and Yaron Singer · 2008
Cited alongside, same era.
Optimal approximation for the submodular welfare problem in the value oracle model
Jan Vondrák · 2008
Cited alongside, same era.
Sorting and selection with imprecise comparisons
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, and Jelani Nelson · 2009
Cited alongside, same era.
On the power of membership queries in agnostic learning
Vitaly Feldman · 2009
Cited alongside, same era.
Approximating submodular functions everywhere
Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni · 2009
Cited alongside, same era.
Non-monotone submodular maximization under matroid and knapsack constraints
Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko · 2009
Cited alongside, same era.
A tight linear time (1/2)-approximation for unconstrained submodular maximization
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz · 2012
Later among the works it cites.
Selecting diverse features via spectral regularization
Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar · 2012
Later among the works it cites.
The computational complexity of truthfulness in combinatorial auctions
Shahar Dobzinski and Jan Vondrák · 2012
Later among the works it cites.
Deep mathematical properties of submodularity with applications to machine learning
J. Bilmes · 2013
Later among the works it cites.
Representation, approximation and learning of submodular functions using low-rank decision trees
Vitaly Feldman, Pravesh Kothari, and Jan Vondrák · 2013
Later among the works it cites.
Optimal bounds on approximation of submodular and XOS functions by juntas
Vitaly Feldman and Jan Vondrák · 2013
Later among the works it cites.
The elements of statistical learning : data mining, inference, and prediction
Trevor J. Hastie, Robert John Tibshirani, and Jerome H. Friedman · 2013
Later among the works it cites.
A principled deep random field for image segmentation
P. Kohli, A. Osokin, and S. Jegelka · 2013
Later among the works it cites.
Submodularity in Machine Learning: New directions
A. Krause and S. Jegelka · 2013
Later among the works it cites.
Fast greedy algorithms in mapreduce and streaming
Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani · 2013
Later among the works it cites.
Equilibrium in combinatorial public projects
Brendan Lucier, Yaron Singer, Vasilis Syrgkanis, and Éva Tardos · 2013
Later among the works it cites.
Symmetry and approximability of submodular maximization problems
Jan Vondrák · 2013
Later among the works it cites.
Streaming submodular maximization: massive data summarization on the fly
Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause · 2014
Later among the works it cites.
Submodular maximization with cardinality constraints
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz · 2014
Later among the works it cites.
From MAP to marginals: Variational inference in bayesian submodular models
J. Djolonga and A. Krause · 2014
Later among the works it cites.
Influence function learning in information diffusion networks
N. Du, Y. Liang, M. Balcan, and L. Song · 2014
Later among the works it cites.
Learning time-varying coverage functions
N. Du, Y. Liang, M. Balcan, and L. Song · 2014
Later among the works it cites.
Learning coverage functions and private release of marginals
Vitaly Feldman and Pravesh Kothari · 2014
Later among the works it cites.
Budget feasible mechanisms for experimental design
Thibaut Horel, Stratis Ioannidis, and S. Muthukrishnan · 2014
Later among the works it cites.
Understanding Machine Learning: From Theory to Algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Later among the works it cites.
Learning submodular functions with applications to multi-agent systems
Maria-Florina Balcan · 2015
Later among the works it cites.
On multiplicative weight updates for concave and submodular function maximization
Chandra Chekuri, T. S. Jayram, and Jan Vondrák · 2015
Later among the works it cites.
Approximate modularity
Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar · 2015
Later among the works it cites.
Tight bounds on low-degree spectral concentration of submodular and XOS functions
Vitaly Feldman and Jan Vondrák · 2015
Later among the works it cites.
Tight bounds on low-degree spectral concentration of submodular and xos functions
Vitaly Feldman and Jan Vondrák · 2015
Later among the works it cites.
Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization
Adish Singla, Sebastian Tschiatschek, and Andreas Krause · 2016
Closest in time.