Smoothed Analysis of Combinatorial Optimization Problems

Many important computational problems are prohibitively difficult to solve in the worst case, but are easy when instances are drawn from real world situations. This suggests that worst case instances rarely occur in real data and that worst case analysis is not a good measure of computational complexity in practice. One hypothesis to explain this discrepancy is that worst case instances are fragile, with noise inherent in real data preventing difficult instances from occurring too frequently. This was first confirmed in 2004 for a well-known optimization problem and has given rise to the theory of smoothed analysis. The purpose of this project is to use smoothed analysis to study the maximum cut problem for graphs, with the goal of giving bounds on the complexity that are tighter than existing bounds.

Faculty Supervisor:

Louigi Addario-Berry

Student:

Partner:

Université de Paris

Discipline:

Mathematics

Sector:

University:

McGill University

Program:

Globalink Research Award