Title: Greedy Heuristic for Maximizing Submodular Set Functions
|Affiliation:||University of Waterloo|
Several hard combinatorial optimization problems can be posed in the following framework: maximize a submodular function over its domain subject to a cardinality constraint. The uncapacitated location problem is a special case of this optimization problem. In this talk, we shall first go over some equivalent definitions of submodularity following which we shall see a greedy heuristic that approximately solve this optimization problem. This is a presentation of the work by Fisher, Nemhauser and Wolsey. No prior knowledge will be assumed for the purposes of this talk.
200 University Avenue West
Waterloo, ON N2L 3G1