Return to Colloquia & Seminar listing
Distributions of Values in Combinatorial Optimization Problems
Student-Run Research Seminar| Speaker: | Tamon Stephen, University of Michigan |
| Location: | 693 Kerr |
| Start time: | Thu, Jan 24 2002, 3:10PM |
We study the distribution of objective values in a combinatorial optimization problems defined on the symmetric group. Our approach is to use techniques from representation theory to generate statistics on the quantity and relative location of good values for two prominent optimization problems on the symmetric group, namely the Quadratic Assignment Problem (QAP) and the Traveling Salesman Problem (TSP). This analysis shows us some very general, yet non-trivial properties of the optimization function, allows us to get guarantees for simple polynomial and non-polynomial approximation algorithms, and helps us to understand why some hard problems are simpler than others. This is joint work with Alexander Barvinok.
JOINT with Discrete Math Seminar.