Grant: Canada Research Chairs

Our ever-growing society is faced with a number of discrete optimization problems on a daily basis. Examples are coordinating fleets of vehicles, locating distribution centres, and routing wires in large-scale circuit design. Unfortunately, even with our massive computing clusters, we are still unable to efficiently solve these problems exactly. I devise approximation algorithms to find near-optimum solutions to these problems. These are efficient heuristics that also come with an absolute guarantee that the solutions found are within some bounded error of the optimum. My work also bridges the gap between our understanding of integer programming heuristics used in practice and the theory of computing, and can lead to savings in time, fuel, and money.