Binay Bhattacharya (SFU)

Min-max regret versions of facility location optimization problems
Binay Bhattacharya (Simon Fraser University, Computing Science)


The two most widely considered measures for optimization under uncertainty are minimizing expected cost and minimizing worst-case cost or regret.  In stochastic optimization, the parameters of the objective function are governed by a probability distributions, and objective is to find a solution that minimizes the cost. In robust optimization, probabilities are not known, and uncertain parameters are specified either by discrete scenarios or by interval ranges; the objective is to minimize the worst-case cost or regret. In this talk we focus on min-max  regret versions with interval structure of uncertainty.  We start with a short review of complexity results for the min-max or min-max  regret versions of some combinatorial problems. We then discuss a few algorithms to solve center and median problems in restricted networks with uncertain parameters.

This is a joint work with Tiko Kameda and Zhao Song.


Friday, November 22, 2013


12:30 pm - 1:30 pm

TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby