Logic List Mailing Archive

PhD student position in probabilististic analysis of algorithms, Twente (The Netherlands), Deadline 15 Mar 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@utwente.nl
    http://www.math.utwente.nl/~mantheyb/