Postdoctoral position on approximability of NP-hard problems, Stockholm (Sweden)

The group on approximation of NP-hard optimization problem at the Royal Institute of Technology in Stockholm, Sweden is looking for a postdoc for the academic year 2011/12 with a possible extension to a second year.

The goal of the current project is to show mathematical theorems relating to efficient computation. The project studies NP-hard combinatorial optimization problems of central importance and aims to establish theoretical bounds on how well each problem can be approximated in polynomial time. The goal is to prove upper bounds by designing and analyzing algorithms and to prove lower bounds in the form of hardness results.

Deadline for applications is February 15, 2011. For more information, see http://www.kth.se/om/work-at-kth/vacancies/ or the project web-page at http://www.csc.kth.se/tcs/projects/approx.php, or email the research leader, Johan Håstad, at johanh at kth.se.