Tutte seminar - Jon Lee

Some submodular maximization algorithms

Abstract:

Motivated by a problem of finding an optimal configuration of environmental monitoring stations, I will present some algorithms for a particular constrained submodular-maximization problem, the maximum-entropy sampling problem. These algorithms are aimed at solving moderate-sized instance in a reasonable amount of time (the OR point of view). One outcome of this work is that local-search is rather good for real instances. Taking another approach, we look at approximation algorithms --- theoretically efficient algorithms with a performance guarantee (the CS Theory point of view). Again, we will see that local search is quite effective. So, we have evidence that we should all get along.