The Traveling Salesman Problem (TSP) and Bin Packing have both served as key testbeds for the introduction of new algorithmic approaches and modes of analysis, particularly in the area of approximation algorithms. For both problems there are important worst- and average-case results, as well as extensive experimental analysis, which will be covered in this course. The following are some of the topics I will address.

* TSP
o Classic theoretical results and their relevance to practice
o Fast implementation of tour-construction heuristics
o Novel tour representations for local search
o Test instances and their properties
o Empirical trade-offs between running time and tour quality
o The state of the art in optimization algorithms
* Bin Packing
o Simple heuristics and asymptotic approximation schemes
o Online algorithms in theory and practice
o Implementation issues
o Average case: Theorems -> Experiments and back again
o The Sum-of-Squares Algorithm


http://logic.pdmi.ras.ru/midas/en/courses#tsp