[Opt-Net] PhD Position, Probabilistic Analysis of Algorithms, University of Twente

Bodo Manthey b.manthey at utwente.nl
Mon Jan 26 11:02:03 CET 2015


PhD Position at the University of Twente
========================================
Probabilistic Analysis of Algorithms
====================================


A full-time PhD position is available within an NWO project on 
probabilistic analysis of algorithms.

The position is within the group Discrete Mathematics and Mathematical 
Programming (DMMP) at the Department of Applied Mathematics. The project 
is funded by Netherlands Organization for Scientific Research (NWO) and 
is embedded in the University of Twente's Centre for Telematics and 
Information Technology (CTIT), the largest academic ICT research 
institute in the Netherlands.

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

WHAT WE OFFER

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 see 
www.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 €2718,- 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.33%.

PROJECT DESCRIPTION: Framework for Random Metric Spaces

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.

INFORMATION AND APPLICATION

You are invited to send your application (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.

Please submit your documents as PDF via

      http://www.utwente.nl/vacatures/?VacatureID=711594


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 at utwente.nl
    http://www.math.utwente.nl/~mantheyb/


More information about the Opt-Net mailing list