# Jerusalem Mathematics Colloquium

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"

** 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.

List of talks, 1998-99

List of talks, 1997-98