Job description

Large-scale optimization problems show up in many domains, such as engineering, scheduling, economics,  but also, e.g., in the sciences. Unfortunately, finding optimal solutions within reasonable time is often impossible because the problems that have to be solved are computationally intractable. Because of this, optimization problems are nowadays often attacked using ad-hoc heuristics. Many such heuristics show a remarkable performance, but their theoretical (worst-case) performance is poor – worst-case analysis is often too pessimistic to reflect the performance observed. In order to explain the performance of heuristics, probabilistic analysis is the method of choice, where performance is analyzed with respect to random instances.

The instances of many optimization problems involve, implicitly or explicitly, a metric space. This can be physical distances, but also, e.g., costs for travel or transportation. Up to now, however, probabilistic analysis of algorithms is almost exclusively restricted to Euclidean instances or the distances are drawn independently, disregarding the metric nature. Both approaches fall short of explaining the average-case performance of heuristics on general metric instances.

Our goal is to develop and apply a framework for random metric spaces. We want to develop models for random metric spaces, study their properties, and apply these findings to explain the observed performance of heuristics for optimization problems. The goal is to obtain more conclusive insights about performance than with the traditionally used models, and to use the insights obtained to design better algorithms.

Requirements

The successful candidate should have a Master’s degree in Mathematics, Computer Science, or a related field. A solid background in Discrete Optimization, Theoretical Computer Science, or the Analysis of Algorithms is highly appreciated but not a must as the candidate will be given the opportunity to follow courses in the LNMB PhD program during her/his first year (see www.lnmb.nl).

To apply for this position, you should submit your application using the linkhttp://www.utwente.nl/vacatures/ (including curriculum vitae, copies of certificates, a letter of motivation, and a short summary of your MSc research) as well as contact information of at least two references that may be consulted.

Deadline for applications is March 15, 2015. The intended starting date is summer/spring 2015, the exact starting date is negotiable.

Please do not hesitate to send any questions to the email given below.

Bodo Manthey
University of Twente
Department of Applied Mathematics
Discrete Mathematics and Mathematical Programming
Enschede, The Netherlands
Email: b.manthey<στο>utwente.nl
http://www.math.utwente.nl/~mantheyb/

Working conditions

We offer a 4-year research position in a dynamic and international environment. The DMMP group consists currently consists of 10 faculty members and is headed by Prof. Marc Uetz. Please seewww.utwente.nl/ewi/dmmp/ for more details. The University of Twente provides excellent campus facilities, and actively supports professional and personal development.

The gross monthly salary starts with €2125,- in the first year and increases to €2717,- in the fourth year of your employment. The salary is supplemented with a holiday allowance of 8% and an end-of year bonus of 8.3%. The research has to result in a PhD thesis at the end of the employment period.