Combinatorial Optimization Reading Group - Ishan Bansal

Title: Greedy Heuristic for Maximizing Submodular Set Functions

Abstract:

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.