ECEN 689: Submodular Functions and Optimization: Theory & Applications - Fall 2016

Syllabus

Notes:

Lectures:

  • [Tu 08/30] Polyhedra and polytopes, dimension theorem
  • [Th 09/01] Projections of polyhedra, theorem of the alternatives
  • [Tu 09/06] LP duality
  • [Th 09/08] Faces of polyhedra
  • [Tu 09/13] Characteristic cone and extremal rays, decomposition theorems
  • [Th 09/15] Submodularity: Basic and extended definitions
  • [Tu 09/20] Examples of submodular functions
  • [Th 09/22] Applications to transversal theory, lattices and submodular function minimization
  • [Tu 10/04] Submodular systems, submodular and base polyhedra, saturation function and capacity
  • [Th 10/06] Dependence function and exchange capacity, dual systems
  • [Tu 10/11] Reductions and contractions by sets, reductions by vectors
  • [Th 10/13] Contractions by vectors
  • [Tu 10/18] Simplifications
  • [Th 10/20] Linear optimization over base polyhedra, structural results
  • [Tu 10/25] Greedy algorithms
  • [Th 10/27] Correctness of the greedy algorithms
  • [Tu 11/08] Submodular function minimization: The Fujishige-Wolfe algorithm

Course projects:

  • Shuo Shao: Submodular salient region detection
  • Chung-Chi (Charles) Tsai: Minimizing energy functions via graph cuts
  • Xiaopeng (Lucia) Sui: Cluster analysis via maximizing a submodular function subject to a matroid constraint
  • Ping-Chun Hsieh: Influence maximization in large-scale social networks
  • Shuai Zuo: Approximate submodular function maximization
  • Vamsi Amalladinne: Minimizing the difference between two submodular functions
  • Kai He: Streaming submodular maximization
  • Ziwei Xuan: Minimizing modular functions
  • Travis Taghavi: Submodular functions in graph theory
  • Paul McVay, Guang Zhao, and Jingqing Wang: Adaptive submodularity
Ċ
Tie Liu,
Sep 13, 2016, 8:07 AM
Ċ
Tie Liu,
Nov 8, 2016, 8:27 AM
Ċ
Tie Liu,
Sep 21, 2016, 8:35 AM
Ċ
Tie Liu,
Oct 19, 2016, 5:25 AM
Ċ
Tie Liu,
Sep 21, 2016, 8:34 AM
Ċ
Tie Liu,
Aug 30, 2016, 7:51 AM