Abstract:

The most famous combinatorial optimization problem, the traveling salesman problem (TSP), is computationally expensive to solve on large instances. This is theoretically explained by the fact that TSP is NP-hard. The existence of a polynomial time algorithm that always finds the optimal solution would imply that NP=P, a rather unlikely state of affairs. The property of being NP-hard (and hard in practice) is shared by many other natural optimization problems and thus it is interesting to study heuristics for getting reasonably good but possibly non-optimal solutions.

An algorithm is a C(n)-approximation if it, on every instance of size n of a problem, finds a solution that is at most a factor C(n) worse than the optimal solution. The question is now, for a given problem, to determine for which values of C(n) it is possible to find an efficient (polynomial time) C(n)-approximation algorithm. For some problems it is possible to get almost tight results. We plan to give examples of such results and try to give at least a hint on their methods of proof.

Coffee, Cookies, Company at the faculty lounge at 3:30.