Fall 2011 Seminar Series

DATE: December 15th
LOCATION: E62-550
TIME: 4:15pm
Reception immediately following

SPEAKER:
Jon Lee

TITLE
Submodular-function Maximization

ABSTRACT
Submodular-function maximization is a central unifying model in combinatorial optimization. Applications range from practical problems such as reconfiguring an environmental monitoring network, to more stylized problems such as the graph max-cut problem. I will describe some of the motivating applications, survey some different methodologies for maximizing a submodular function subject to side constraints, and describe computational results on environmental-monitoring problem instances for some of the more practical algorithms. Interestingly, while some of the algorithms are aimed at practical computation via an Operations Research / Mathematical Optimization approach, and others are driven by the Computer Science theory of approximation algorithms, there is significant common ground.

Back to Seminar Series schedule page