Some submodular maximization algorithms
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1