Thursday, 15 April 1999, 4:00 pm
Mathematics Bldg., lecture hall 2
The Jerusalem Mathematics Colloquium is happy to host the first of the three Erdos lectures of 1999:
Professor Johan Hastad
(The Royal Institute of Technology, Stockholm, Sweden)
"Optimal inapproximability results for some NP-hard optimization"
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.