References
This list contains references used in the tutorial, and pointers beyond.
This list is bar far not complete, it provides a sketch of developments. If you feel like an important reference is missing, please let us know.
Surveys on submodular functions and optimization, and foundational work
- * S. Fujishige. Submodular functions and optimization. Annals of Discrete Mathematics, Elsevier 2nd Edition 2005, 1st Edition 1991
Monograph on submodular functions.
- * H. Narayanan. Submodular Functions and Electrical Networks. Elsevier Science, 1997.
- * A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003
- * F. Bach. Learning with Submodular Functions: A Convex Optimization Perspective. Technical Report HAL 00645271, 2011.
- * S. T. McCormick. Handbook on Discrete Optimization, chapter Submodular Function
Minimization, pages 321–391. Elsevier, 2006. updated version 3a (2008).
- * L. Fleischer. Recent progress in submodular function minimization. Mathematical
Programming Society Newsletter, (64):1–11, 2000
- * S. Iwata. Submodular Function Minimization, Math. Programming, 112 (2008), 45-64.
- * A. Krause, D. Golovin, Submodular Function Maximization, Chapter
in Tractability: Practical Approaches to Hard Problems (to appear),
Cambridge University Press, 2012.
- * J. Edmonds. Submodular functions, matroids, and certain
polyhedra. Proceedings of the Calgary International Conference on
Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N.
Sauer and J. Schoenheim, eds., Gordon and Breach, New York, 1970), pp.
69–87; also in: Combinatorial Optimization—Eureka, You Shrink! (M.
Juenger, G. Reinelt, and G. Rinaldi, eds., Lecture Notes in Computer
Science 2570, Springer, Berlin, 2003), pp. 11–26.
Foundational work on polymatroid rank functions (nondecreasing submodular functions), shows that linear optimization over the base polytope can be done in O(n log n)
- * L. Lovasz. Submodular functions and convexity. Mathematical Programming - State of the Art, pages 235–257, 1983.
Discusses connections between submodular and convex functions. Introduces Lovasz extension.
- * L. S. Shapley. Cores of convex games. International Journal of Game Theory, 1 (1):11–26, 1971.
- * L Choquet. Theory of capacities. Ann. Inst. Fournier Grenoble, 5, 1955.
Submodular Minimization (unconstrained)
- * M. Groetschel, L. Lovasz, and A. Schrijver. The ellipsoid method
and its consequences in combinatorial optimization. In Combinatorica,
1:169-197, 1981
Shows how the ellipsoid algorithm can minimize submodular functions in polynomial time.
- * S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial
strongly polynomial algorithm for minimizing submodular functions.
Journal of the ACM, 48(4):761–777, 2001.
One of the two first strongly polynomial algorithms for minimizing arbitrary submodular functions.
- * A. Schrijver. A combinatorial algorithm minimizing submodular
functions in strongly polynomial time. J. Combin. Theory Ser. B,
80:346–355, 2000.
One of the two first strongly polynomial algorithms for minimizing arbitrary submodular functions.
- * J. B. Orlin. A faster strongly polynomial time algorithm for submodular function
minimization. Mathematical Programming, 118(2):237–251, 2009.
Currently fastest strongly polynomial algorithm.
- * W. H. Cunningham. Testing membership in matroid polyhedra. J. Combinatorial Theory B, 36:161–188, 1984.
Forerunner of the combinatorial algorithms for the special case of the
difference of a matroid rank function and a rational modular function.
- * W. H. Cunningham. On submodular function minimization. Combinatorica, 3:185–192, 1985a.
Introduces a flow-like framework that leads to a pseudo-polynomial algorithm and inspired subsequent combinatorial algorithms.
- * S. Fujishige and S. Isotani: A submodular function minimization
algorithm based on the minimum-norm base. Pacific Journal of
Optimization, Vol. 7 (2011), pp. 3--17
Empirical study on the performance of the Fujishige-Wolfe minimum norm point algorithm.
- * S. Jegelka, H. Lin, and J. A. Bilmes. On Fast Approximate
Submodular Minimization. In Neural Information Processing Society
(NIPS), Granada, Spain, December 2011.
Approximate minimization of general submodular functions via iterative graph cuts
Submodular Minimization (special cases)
- * S. Zivny, D. A. Cohen, and P. G. Jeavons. The expressive power of
binary submodular functions. Discrete Applied Mathematics,
157(15):3347–3358, 2009.
Show that not all submodular functions can be represented as graph cuts.
- * V. Kolmogorov. Minimizing a sum of submodular functions. Discrete Applied Mathematics, 2012.
Faster algorithm for sums of submodular functions with bounded support.
- * P. Stobbe and A. Krause. Efficient minimization of decomposable submodular
functions. In Advances in Neural Information Processing Systems (NIPS), 2010.
Nesterov's smoothing for sums of submodular functions arising from concave functions.
- * M. Preissmann and A. Sebo. Research Trends in Combinatorial Optimization,
chapter Graphic Submodular Function Minimization: A Graphic Approach and
Applications, pages 365–385. Springer, 2009.
Special algorithm for a function that is the sum of a graphic matroid's rank function and a modular function.
- * P. Kohli, L. Ladicky, P. Torr. Robust Higher Order Potentials for Enforcing Label Consistency. IJCV 2009
Show how to use graph cuts for certain higher-order potentials
- * S. Fujishige and S. B. Patkar. Realization of set functions as cut functions of graphs and hypergraphs. Discrete Mathematics, 226:199-210, 2001.
- * V. Kolmogorov and R. Zabih. What Energy Functions can be
Minimized via Graph Cuts? IEEE Transactions on Pattern Analysis and
Machine Intelligence (PAMI), 26(2):147-159, February 2004.
- * S. Zivny and P. Jeavons. Classes of submodular constraints expressible by graph cuts. Constraints 15(3), pp. 430-452, 2010.
- * D. Freedman and P. Drineas. Energy minimization via graph cuts:
Settling what is possible. In IEEE Conf. on Computer Vision and Pattern
Recognition (CVPR), 2005.
- * A. Billionet and M. Minoux. Maximizing a supermodular
pseudo-boolean function: a polynomial algorithm for cubic functions.
Discrete Applied Mathematics, 12 (1):1–11, 1985.
- * B. Zalesky. Efficient determination of Gibbs estimators with submodular energy functions. arXiv:math/0304041, 2003.
- * M. Queyranne. Minimizing symmetric submodular functions. Mathematical Programming, 82:3–12, 1998.
Cubic algorithm for minimizing symmetric submodular functions.
Constrained Submodular Minimization
- * M. Goemans, and V. Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15(4): 499-513, 1995
- * M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial
Optimization. Springer, 1988.(Chapter 10)
Submodular minimization over a ring or crossing family is like
submodular minimization over a power set. Similarly, the constraint
that the solution should have odd cardinality does not make the problem
NP-hard.
- * A. Krokhin and B. Larose. Maximizing supermodular functions on
product lattices, with applications to maximum constraint satisfaction.
SIAM Journal on Discrete Math., 22(1):312–328, 2008
Show product and non-distributive lattices over which SFM is polynomial-time solvable.
- * M. X. Goemans and J. A. Soto. Symmetric submodular function
minimization under hereditary family constraints. arXiv:1007.2140v1,
2010.
Special case: symmetric submodular functions can be minimized over
downward-monotone families (e.g., upper bound on cardinality of the
solution).
- * G. Gallo and B. Simeone. On the supermodular knapsack problem. Math. Prog. 45, 295-309, 1988.
- * Z. Svitkina and L. Fleischer. Submodular approximation:
Sampling-based algorithms and lower bounds. In Proc. IEEE Symp. on
Foundations of Computer Science (FOCS), 2008.
Hardness results and approximation algorithms for SFM under cardinality and related constraints.
- * K. Nagano, Y. Kawahara, and K. Aihara. Size-constrained
submodular minimization through minimum norm base. In Proc. Int. Conf.
on Machine Learning (ICML), 2011.
The minimum norm vector gives the optimal solution for some cardinality constraints.
- * S. Iwata and K. Nagano. Submodular function minimization under
covering constraints. In Proc. IEEE Symp. on Foundations of Computer
Science (FOCS), 2009.
Hardness results and approximation algorithm for covering constraints.
- * G. Goel, C. Karande, P. Tripati, and L. Wang. Approximability of
combinatorial problems with multi-agent submodular cost functions. In
Proc. IEEE Symp. on Foundations of Computer Science (FOCS), 2009.
- * G. Goel, P. Tripathi, and L. Wang. Combinatorial problems with
discounted price functions in multi-agent systems. In Foundations of
Software Technology and Theoretical Computer Science (FSTTCS), 2010.
Hardness results and approximation algorithm for spanning tree, shortest path and perfect matching with submodular costs.
- * S. Jegelka and J. Bilmes. Approximation Bounds for Inference
using Cooperative Cuts. International Conference on Machine Learning
(ICML), 2011.
Hardness results and approximation algorithms for graph cuts with submodular edge weights.
- * S. Jegelka and J. Bilmes. Submodularity Beyond Submodular
Energies: Coupling Edges in Graph Cuts. IEEE Conference on Computer
Vision and Pattern Recognition (CVPR), 2011.
Applications of graph cuts with submodular edges to image segmentation and defining higher-order energy functions.
- * C. Chekuri and A. Ene. Approximation algorithms for submodular
multiway partition. In Proc. IEEE Symp. on Foundations of Computer
Science (FOCS), 2011a.
Approximations for submodular multi-way partition.
- * C. Chekuri and A. Ene. Submodular cost allocation problems and
applications. In Int. Colloquium on Automata, Languages and Programming
(ICALP), 2011b.
- * V. Goyal and R. Ravi. An FPTAS for minimizing a class of low-rank
quasi-concave functions over a convex domain. Technical Report 366,
Tepper School of Business, Carnegie Mellon University, 2008.
- * S. Mittal and A. Schulz. An FPTAS for optimizing a class of low-rank functions over a polytope. Mathematical Programming, 2012.
- * E. Nikolova. Approximation algorithms for reliable stochastic combinatorial optimization. In APPROX, 2010.
Restricted classes of submodular functions admit an FPTAS under certain combinatorial constraints.
- * G. Goel, C. Karande, P. Tripati, and L. Wang. Approximability of
combinatorial problems with multi-agent submodular cost functions. In
Proc. IEEE Symp. on Foundations of Computer Science (FOCS), 2009.
- * G. Goel, P. Tripathi, and L. Wang. Combinatorial problems with
discounted price functions in multi-agent systems. In Foundations of
Software Technology and Theoretical Computer Science (FSTTCS), 2010.
- * S. Iwata and K. Nagano. Submodular function minimization under
covering con- straints. In Proc. IEEE Symp. on Foundations of Computer
Science (FOCS), 2009.
- * Z. Svitkina and L. Fleischer. Submodular approximation:
Sampling-based algo- rithms and lower bounds. In Proc. IEEE Symp. on
Foundations of Computer Science (FOCS), 2008.
- * D. Hochbaum. Submodular problems – approximations and algorithms. arXiv:1010.1945.v1, 2010.
- * Delong, A., Veksler, O., Osokin, A., and Boykov, Y. Minimizing sparse high-order energies by submodular vertex-cover. In In NIPS, 2012.
- * R. Iyer, S. Jegelka and J. Bilmes. Fast Semidifferential-based Submodular Function Optimization. ICML 2013.
- * P. Kohli, A. Osokin and S. Jegelka. A Principled Deep Random Field for Image Segmentation. CVPR 2013.
Applications and other papers related to submodular minimization
- * L. Zhao, H. Nagamochi, and T. Ibaraki. Greedy splitting
algorithms for approximating multiway partition problems, Mathematical
Programming 102(1): 167-183, 2005
Analyzes greedy splitting for submodular clustering.
- * A. Guillory and J. Bilmes. Active Semi-Supervised Learning using
Submodular Functions. UAI 2011.
Replacing graph cut as a regularizer by a more generic submodular
function.
- * M. Narasimhan and J. Bilmes. Pac-learning bounded tree-width
graphical models. In Uncertainty in Artificial Intelligence, 2004
Uses symmetric submodular function minimization to find separators, which allows efficient structure learning.
- * A. Chechetka and C. Guestrin. Efficient principled learning of
thin junction trees. In In Advances in Neural Information Processing
Systems (NIPS), Vancouver, Canada, December 2007
Uses submodular function optimization to speed up structure learning.
- * M. Narasimhan, N. Jojic, and J. Bilmes. Q-clustering. In NIPS, 2005.
Shows how Queyranne's algorithm can be used for (near-)optimal clustering.
- * A. Guillory and J. Bilmes. Active Semi-Supervised Learning using
Submodular Functions. In Uncertainty in Artificial Intelligence (UAI),
AUAI, Barcelona, Spain, July 2011.
- * F. Bach. Shaping Level Sets with Submodular Functions. Advances in Neural Information Processing Systems (NIPS), 2011
- * F. Bach. Structured Sparsity-Inducing Norms through Submodular
Functions. Advances in Neural Information Processing Systems (NIPS),
2010
- * H. Lin and J. A. Bilmes. Optimal Selection of Limited Vocabulary
Speech Corpora. In Proc. Annual Conference of the International Speech
Communication Association (INTERSPEECH), Florence, Italy, August 2011.
Submodular Maximization (exact algorithms)
- * B. Goldengorin and G. Sierksma and G. A. Tijssen and M. Tso. The
Data-Correcting Algorithm for the Minimization of Supermodular
Functions. Management Science, Vol 45 No. 11, pp. 539-1551 (1999)
- * Y. Kawahara, K. Nagano, K. Tsuda, J. Bilmes, Submodularity Cuts and Applications. NIPS 2009
- * G. Nemhauser, L. Wolsey. Maximizing Submodular Set Functions:
Formulations and Analysis of Algorithms. Studies on Graphs and Discrete
Programming, pp. 279-301. North Holland 1981
Submodular Maximization (unconstrained)
- * N. Buchbinder, M. Feldman and J. Naor and R. Schwartz. A Tight
Linear Time (1/2)-Approximation for Unconstrained Submodular
Maximization. FOCS 2012
- * U. Feige, V. Mirrokni and J. Vondrak. Maximizing non-monotone
submodular functions. SIAM Journal on Computing 40:4 (2011), 1133-1153.
Submodular Maximization (constrained)
- * G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the
approximations for maximizing submodular set functions. Mathematical
Programming, 14:265–294, 1978.
(1-1/e) guarantee for the greedy algorithm for maximizing submodular functions.
- * M. Fisher, G. Nemhauser and L. Wolsey. An analysis of
approximations for maximizing submodular set functions II, Math.
Programming Study 8: 73–87, 1978
Guarantees for maximizing submodular functions over the intersection of p matroids.
- * M. Minoux. Accelerated greedy algorithms for maximizing
submodular set functions. In Optimization Techniques, LNCS 234-243,
1978
Introduces the lazy greedy algorithm and online bounds for maximizing submodular functions.
- * M. Sviridenko. A note on maximizing a submodular set function
subject to knapsack constraint. Operations Research Letters, 32:41–43,
2004
Shows that (1-1/e) guarantee can be achieved for budgeted maximization of submodular functions.
- * A. Krause, C. Guestrin. A Note on the Budgeted Maximization on
Submodular Functions. Technical Report CMU-CALD-05-103, 2005
Guarantees for submodular function maximization if function is perturbed by noise / only approximately submodular.
- * J. Vondrak. Optimal approximation for the Submodular Welfare Problem in the value oracle model, STOC 2008
Proves (1-1/e) guarantee for a continuous greedy algorithm for
maximizing submodular functions subject to arbitrary matroid
constraints.
- * C. Chekuri and M. Pal. A recursive greedy algorithm for walks in
directed graphs. In Annual Symposium on Foundation of Computer Science
(FOCS), pages 245–253, 2005
Slightly superpolynomial approximation algorithm for submodular path planning (orienteering).
- * A. Singh, A. Krause, C. Guestrin, W. Kaiser, and M. Batalin.
Efficient planning of informative paths for multiple robots. In IJCAI,
2007
An efficient approximation algorithm for submodular path planning (orienteering), with extensions for multiple robots.
- * A. Krause, R. Rajagopal, A. Gupta, C. Guestrin. Simultaneous Placement and Scheduling of Sensors, IPSN 09.
- * A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg. Near-optimal
sensor placements: Maximizing information while minimizing
communication cost. In Proceedings of the Fifth International Symposium
on Information Processing in Sensor Networks (IPSN), 2006
Optimizing monotonic submodular functions subject to communication constraints.
- * A. Krause, B. McMahan, C. Guestrin, and A. Gupta. Selecting observations against adversarial objectives. In NIPS, 2007
Maximizing the minimum over a set of monotonic submodular functions, with applications to robust experimental design.
- * Y. Filmus and J. Ward. A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint. FOCS 2012
- * C. Chekuri, J. Vondrak, R. Zenklusen. Submodular function
maximization via the multilinear relaxation and contention resolution
schemes. STOC 2011, 783-792.
- * S. O. Gharan, J. Vondrak. Submodular maximization by simulated annealing. SODA 2011
- * G. Calinescu, C. Chekuri, M. Pal and J. Vondrak. Maximizing a
submodular set function subject to a matroid constraint. SIAM Journal
on Computing 40:6 (2011)
- * C. Chekuri, J. Vondrak, R. Zenklusen. Multi-budgeted matchings
and matroid intersection via dependent rounding. SODA 2011, 1080-1097.
- * L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2:385–393, 1982.
Proves guarantees for the greedy algorithm for submodular coverage.
Applications of submodular maximization:
- * M. Seeger. Greedy Forward Selection in the Informative Vector Machine. Manuscript 2004
Proves that the greedy algorithm used in the IVM optimizes a submodular function.
- * A. Das and D. Kempe. Algorithms for subset selection in linear regression. In STOC, 2008.
Variance reduction in Gaussian models is submodular under certain conditions on the covariance.
- * S. C. H. Hoi, R. Jin, J. Zhu, and M. R. Lyu. Batch mode active
learning and its application to medical image classification. In ICML,
2006.
Defines a monotonic submodular criterion for batch-mode active learning of kernelized logistic regression.
- * A. K. Kelmans and B. N. Kimelfeld. Multiplicative submodularity
of a matrix’s principal minor as a function of the set of its rows and
some combinatorial applications. Discrete Mathematics, 44(1):113–116,
1980.
Proves that entropy is a submodular function.
- * D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, 2003
Maximizing influence (viral marketing) in social networks is submodular.
- * A. Krause and C. Guestrin. Near-optimal nonmyopic value of information in graphical models. In UAI, 2005
Information gain in Naive Bayes models is submodular. Also gives
(1-1/e) hardness of approximation result for information gain in such
models.
- * A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor
placements in Gaussian processes: Theory, efficient algorithms and
empirical studies. In JMLR, 2008.
Proves approximate monotonicity of mutual information for experimental design in Gaussian Processes.
- * J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen,
and N. Glance. Cost-effective outbreak detection in networks. In KDD,
2007
Proves monotonic submodularity for outbreak detection in networks, with
applications to sensor placement and selecting informative blogs.
- * A. Meliou, A. Krause, C. Guestrin, and J. Hellerstein. Nonmyopic
informative path planning in spatio-temporal models. In AAAI, 2007.
Spatio-temporal submodular path planning.
- * T. G. Robertazzi and S. C. Schwartz. An accelerated sequential
algorithm for producing D-optimal designs. SIAM Journal of Scientific
and Statistical Computing, 10(2):341–358, March 1989.
Uses lazy evaluations to construct D-optimal designs.
- * O. Barinova, V. Lempitsky, P. Kohli. On Detection of Multiple Object Instances using Hough Transforms. PAMI 2012
Uses submodular maximization for multiple object detection based on the Hough transform
- * H. Lin and J. Bilmes. A Class of Submodular Functions for
Document Summarization. In The 49th Annual Meeting of the Association
for Computational Linguistics: Human Language Technologies
(ACL/HLT-2011), Portland, OR, June 2011.
- * M. G. Rodriguez, J. Leskovec, A. Krause, Inferring Networks of
Diffusion and Influence, In ACM Transactions on Knowledge Discovery
from Data, vol. 5, no. 4, pp. 21:1-21:37, 2012.
- * A. Das, D. Kempe: Submodular meets Spectral: Greedy Algorithms
for Subset Selection, Sparse Approximation and Dictionary Selection. In
Proc. of ICML 2011
- * V. Cevher, A. Krause, "Greedy Dictionary Selection for Sparse
Representation", In IEEE Journal of Selected Topics in Signal
Processing, vol. 99, no. 5, pp. 979-988, 2011
- * C. Reed, Z. Ghahramani. Scaling the Indian Buffet Process via Submodular Maximization. ICML 2013.
Generalization of submodular maximization
- * A.P. Singh, A. Guillory and J. Bilmes. On Bisubmodular maximization. AISTATS 2012.
- * U. Feige. On maximizing welfare when utility functions are subadditive. In STOC, 2006
Generalization of the submodular welfare problem to subadditive set functions.
Optimizing Differences of Submodular functions
- * M. Narasimhan and J. Bilmes. A submodular-supermodular procedure
with applications to discriminative structure learning. In Advances in
Neural Information Processing Systems (NIPS) 19, 2006
Maximizing the difference of two submodular functions.
- * R. Iyer and J. Bilmes. Algorithms for Approximate Minimization of
the Difference Between Submodular Functions, with Applications. In
Uncertainty in Artificial Intelligence (UAI), AUAI, Catalina Island,
USA, July 2012.
- * Y. Kawahara, T. Washio. Prismatic Algorithm for Discrete D.C. Programming Problem. NIPS 2011
Learning/Approximating/Representing submodular functions
- * M.X. Goemans, N. J. A. Harvey, S. Iwata, and V. S. Mirrokni.
Approximating submodular functions everywhere. In Proc. SIAM-ACM Symp.
on Discrete Algorithms (SODA), 2009.
- * M. F. Balcan, N. Harvey, Learning Submodular Functions. STOC 2011
- * M. F. Balcan, F. Constantin, S. Iwata, L. Wang, Learning Valuation Functions COLT 2012
- * A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisam, T. Roughgarden. Sketching Valuation Functions, SODA 2012
- * M. Cheraghchi, A. Klivans, P. Kothari, and H. Lee. Submodular functions are noise stable. In SODA, 2012.
- * A. Gupta, M. Hardt, A. Roth, and J. Ullman. Privately releasing conjunctions and the statistical query barrier. In STOC, 2011.
- * S. Raskhodnikova and G. Yaroslavtsev. Learning pseudo-boolean k-DNF and submodular functions. SODA, 2013.
- * P. Stobbe, A. Krause, Learning Fourier Sparse Set Functions, In
Proc. International Conference on Artificial Intelligence and
Statistics (AISTATS), 2012
- * H. Lin and J. Bilmes. Learning Mixtures of Submodular Shells with
Application to Document Summarization. In Uncertainty in Artificial
Intelligence (UAI), AUAI, Catalina Island, USA, July 2012.
Online Submodular Optimization
- * D. Golovin and M. Streeter. Online algorithms for maximizing submodular set functions. NIPS 2008.
Online algorithm for maximizing submodular functions, with application to scheduling.
- * A. Guillory and J. Bilmes. Online Submodular Set Cover, Ranking,
and Repeated Active Learning. In Neural Information Processing Society
(NIPS), Granada, Spain, December 2011.
- * S. Jegelka and J. A. Bilmes. Online Submodular Minimization for
Combinatorial Structures. In International Conference on Machine
Learning (ICML), Bellevue, Washington, 2011.
- * M. Streeter, D. Golovin, A. Krause, Online Learning of Assignments, In Proc. Neural Information Processing Systems (NIPS), 2009
- * D. Golovin, M. Faulkner, A. Krause, Online Distributed Sensor
Selection, In Proc. ACM/IEEE International Conference on Information
Processing in Sensor Networks (IPSN), 2010
- * M. Streeter, D. Golovin, S. Smith, Combining Multiple Heuristics Online. AAAI 2007
- * Y. Yue, C. Guestrin. Linear Submodular Bandits and their Applications to Diversified Retrieval. NIPS 2011
- * E. Hazan, S. Kale. Online Submodular Minimization. NIPS 2009
- * S. Ross, J. Zhou, Y. Yue, D. Dey, D. Bagnell. Learning Policies for Contextual Submodular Prediction. ICML 2013
Adaptive / interactive submodular optimization and sequential decision making.
- * A. Guillory and J. A. Bilmes. Simultaneous Learning and Covering
with Adversarial Noise. In International Conference on Machine Learning
(ICML), Bellevue, Washington, 2011.
- * D. Golovin, A. Krause, Adaptive Submodularity: Theory and
Applications in Active Learning and Stochastic Optimization, In Journal
of Artificial Intelligence Research (JAIR), vol. 42, pp. 427-486, 2011
- * A. Asadpour, H. Nazerzadeh and A. Saberi, Stochastic Submodular Maximization. WINE 2008
- * D. Golovin, A. Krause, D. Ray, Near-Optimal Bayesian Active
Learning with Noisy Observations, In Proc. Neural Information
Processing Systems (NIPS), 2010.
- * Y. Chen and A. Krause. Near-optimal Batch Mode Active Learning and Adaptive Submodular Optimization. ICML 2013
Other papers related to submodularity and ML
- * N. Ruozzi. The Bethe Partition Function of log-supermodular graphical models. NIPS 2012.