Return to Colloquia & Seminar listing
Distributions of Values in Combinatorial Optimization Problems
Student-Run Research| Speaker: | Tamon Stephen, University of Michigan |
| Location: | 693 Kerr |
| Start time: | Thu, Jan 24 2002, 3:10PM |
Description
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.