Friday, January 25, 2013 3:30 pm
-
4:30 pm
EST (GMT -05:00)
Some submodular maximization algorithms
Speaker: | Jon Lee |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics and Computer Building (MC) 5158 |
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.