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/