PhD Position, Probabilistic Analysis of Algorithms, University of Twente

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