CATS-Feb-28-2014
Title[edit]
On Correcting Inputs - Inverse Optimization with a Margin
Speaker[edit]
Manish Purohit, University of Maryland
Abstract[edit]
Algorithm designers typically assume that the input data is correct, and then proceed to find ``optimal or ``sub-optimal solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is adjust the input data so that the given output is indeed optimal. In this talk, we consider inverse optimization with a margin, i.e., the given output should be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings, minimum cost maximum flows, and shortest paths.
