Annotated Bibliography

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 additive 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

Last updated: June 2013