Fetching the paper…
Reading the bibliography…
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications.
Extremum problems with inequalities as subsidiary conditions
F. John · 1948
Earlier work this paper cites.
Submodular functions, matroids, and certain polyhedra
J. Edmonds · 1970
Earlier work this paper cites.
An analysis of approximations for maximizing submodular set functions — I
L. A. Wolsey G. L. Nemhauser and M. L. Fisher · 1978
Earlier work this paper cites.
Complexity of matroid property algorithms
P. M. Jensen and B. Korte · 1982
Earlier work this paper cites.
Job matching, coalition formation, and gross substitutes
A. Kelso and V. Crawford · 1982
Earlier work this paper cites.
An analysis of the greedy algorithm for the submodular set covering problem
L. A. Wolsey · 1982
Earlier work this paper cites.
Submodular functions and convexity
L. Lovász · 1983
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Optimal bundle pricing
W. Hanson and R. K. Martin · 1990
Earlier work this paper cites.
Decision theoretic generalizations of the pac model for neural net and other learning applications
D. Haussler · 1992
Earlier work this paper cites.
Matroid Theory
J. G. Oxley · 1992
Earlier work this paper cites.
Query learning can work poorly when a human oracle is used
E. Baum and K. Lang · 1993
Earlier work this paper cites.
Geometric Algorithms and Combinatorial Optimization
M. Grötschel, L. Lovász, and A. Schrijver · 1993
Earlier work this paper cites.
Constant depth circuits, Fourier transform and learnability
N. Linial, Y. Mansour, and N. Nisan · 1993
Earlier work this paper cites.
Cryptographic limitations on learning boolean formulae and finite automata
M. Kearns and L. Valiant · 1994
Earlier work this paper cites.
An Introduction to Computational Learning Theory
M. Kearns and U. Vazirani · 1994
Earlier work this paper cites.
Concentration of measure and isoperimetric inequalites in product spaces
M. Talagrand · 1995
Earlier work this paper cites.
A Probabilistic Theory of Pattern Recognition
L. Devroye, L. Györfi, and G. Lugosi · 1996
Earlier work this paper cites.
Expander codes
M. Sipser and D. A. Spielman · 1996
Earlier work this paper cites.
Horn functions and submodular boolean functions
O. Ekin, P. L. Hammer, and U. N. Peled · 1997
Earlier work this paper cites.
Statistical Learning Theory
V. N. Vapnik · 1998
Earlier work this paper cites.
Neural Network Learning: Theoretical Foundations
M. Anthony and P. Bartlett · 1999
Earlier work this paper cites.
Walrasian equilibrium with gross substitutes
F. Gul and E. Stacchetti · 1999
Earlier work this paper cites.
The Probabilistic Method
N. Alon and J. Spencer · 2000
Earlier work this paper cites.
Random Graphs
S. Janson, T. Łuczak, and A. Ruciński · 2000
Earlier work this paper cites.
Putting auction theory to work: The simultaneous ascending auction
P. R. Milgrom · 2000
Earlier work this paper cites.
A combinatorial algorithm minimizing submodular functions in strongly polynomial time
A. Schrijver · 2000
Earlier work this paper cites.
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
S. Iwata, L. Fleischer, and S. Fujishige · 2001
Earlier work this paper cites.
Learnability and rationality of choice
G. Kalai · 2001
Earlier work this paper cites.
Improved bounds on the sample complexity of learning
Y. Li, P. M. Long, and A. Srinivasan · 2001
Earlier work this paper cites.
Graph Colouring and the Probabilistic Method
M. Molloy and B. Reed · 2001
Cited alongside, same era.
Are bitvectors optimal?
H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh · 2002
Cited alongside, same era.
Learnability and rationality of choice
G. Kalai · 2003
Cited alongside, same era.
Discrete Convex Analysis
K. Murota · 2003
Cited alongside, same era.
Presentation and structure of substitutes valuations
M. Bing, D. Lehmann, and P. Milgrom · 2004
Cited alongside, same era.
Learning intersections and thresholds of halfspaces
A. Klivans, R. O’Donnell, and R. Servedio · 2004
Cited alongside, same era.
Combinatorial Optimization: Polyhedra and Efficiency
Item pricing for revenue maxmimization
M. F. Balcan, A. Blum, and Y. Mansour · 2009
Later among the works it cites.
On concentration of self-bounding functions
S. Boucheron, G. Lugosi, and P. Massart · 2009
Later among the works it cites.
Approximability of combinatorial problems with multi-agent submodular cost functions
G. Goel, C. Karande, P. Tripathi, and L. Wang · 2009
Later among the works it cites.
Approximating submodular functions everywhere
M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni · 2009
Later among the works it cites.
Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes
V. Guruswami, C. Umans, and S. P. Vadhan · 2009
Later among the works it cites.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction
T. Hastie, R. Tibshirani, and J. Friedman · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Schrijver · 2004
Cited alongside, same era.
On learning monotone DNF under product distributions
R. Servedio · 2004
Cited alongside, same era.
On the computational power of iterative auctions
L. Blumrosen and N. Nisan · 2005
Cited alongside, same era.
Submodular Functions and Optimization
S. Fujishige · 2005
Cited alongside, same era.
Oblivious routing in directed graphs with random demands
M. T. Hajiaghayi, J. H. Kim, T. Leighton, and H. Räcke · 2005
Cited alongside, same era.
Near-optimal nonmyopic value of information in graphical models
A. Krause and C. Guestrin · 2005
Cited alongside, same era.
Submodular function minimization under covering constraints
S. Iwata and K. Nagano · 2009
Later among the works it cites.
A simple combinatorial algorithm for submodular function minimization
S. Iwata and J. Orlin · 2009
Later among the works it cites.
Notes on graph cuts with submodular edge weights
S. Jegelka and J. Bilmes · 2009
Later among the works it cites.
Learning and Smoothed Analysis
A. Tauman Kalai, A. Samorodnitsky, and S. Teng · 2009
Later among the works it cites.
Intelligent information gathering and submodular function optimization, 2009
A. Krause and C. Guestrin · 2009
Later among the works it cites.
Maximizing submodular set functions subject to multiple linear constraints
A. Kulik, H. Shachnai, and T. Tamir · 2009
Later among the works it cites.
Symmetry and approximability of submodular maximization problems
J. Vondrák · 2009
Later among the works it cites.
Dependent randomized rounding via exchange properties of combinatorial structures
C. Chekuri, J. Vondrák, and R. Zenklusen · 2010
Closest in time.
Maximizing nonmonotone submodular functions under matroid and knapsack constraints
J. Lee, V. Mirrokni, V. Nagarajan, and M. Sviridenko · 2010
Closest in time.
Submodular maximization over multiple matroids via generalized exchange properties
J. Lee, M. Sviridenko, and J. Vondrak · 2010
Closest in time.
A note on concentration of submodular functions, May 2010
J. Vondrák · 2010
Closest in time.
http://las.ethz.ch/discml/
NIPS workshop on discrete optimization in machine learning (DISCML): Uncertainty, generalization and feedback, 2011 · 2011
Closest in time.
Maximizing a submodular set function subject to a matroid constraint
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák · 2011
Closest in time.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
C. Chekuri, J. Vondrak, and R. Zenklusen · 2011
Closest in time.
Nonmonotone submodular maximization via a structural continuous greedy algorithm
M. Feldman, J. Naor, and R. Schwartz · 2011
Closest in time.
A unified continuous greedy algorithm for submodular maximization
M. Feldman, J. Naor, and R. Schwartz · 2011
Closest in time.
Connections in Combinatorial Optimization
A. Frank · 2011
Closest in time.
Privately releasing conjunctions and the statistical query barrier
A. Gupta, M. Hardt, A. Roth, and J. Ullman · 2011
Closest in time.
Submodular maximization by simulated annealing
S. Oveis Gharan and J. Vondrák · 2011
Closest in time.
Sketching valuation functions
A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan, and T. Roughgarden · 2012
Closest in time.
Learning valuation functions
M.-F. Balcan, F. Constantin, S. Iwata, and L. Wang · 2012
Closest in time.
Submodular functions are noise stable
M. Cheraghchi, A. R. Klivans, P. Kothari, and H. K. Lee · 2012
Closest in time.
On the hardness of welfare maximization in combinatorial auctions with submodular valuations
S. Dobzinski and J. Vondrák · 2012
Closest in time.
A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, 2012
Y. Filmus and J. Ward · 2012
Closest in time.