[DMANET] PhD position "FPT algorithms for geometric network problems" at TU Eindhoven

PhD position "FPT algorithms for geometric network problems"

Most algorithmic network problems are NP-hard, which means that we cannot expect to solve them in polynomial time in the worst case. However, the typical input instances that arise in practice often have certain favorable properties that make it easier to solve them efficiently. The theory of FPT algorithms formalizes this. Here one defines a certain parameter for the problem at hand (the size of the solution, for instance) and then the goal is to develop an algorithm that runs in polynomial time when this parameter is a constant. Over the past several years, FPT algorithms have been developed for many network problems. Most of these results focus on general graphs.In this project we want to study FPT algorithms for geometric networks, where we will consider geometrically defined parameters. The project is part of the NETWORKS program (see below) and will take place in the Algorithms Group at the TU Eindhoven, under the supervision of profs. Mark de Berg and Hans Bodlaender.

NETWORKS. NETWORKS is a 10-year research program funded by the Dutch Ministry of Education, Culture and Science through the Netherlands Organisation for Scientific Research. The NETWORKS consortium consists of top researchers from four different institutions: University of Amsterdam (UvA), Eindhoven University of Technology (TU/e), Leiden University (UL) Center for Mathematics and Computer Science (CWI). The program started in the Summer of 2014 and covers a broad range of topics dealing with stochastic and algorithmic aspects of networks. The aim of the programme is to address the pressing challenges posed by large-scale networks with the help of stochastics and algorithmics. See http://www.thenetworkcenter.nl/ for more details.

The TU/e Algorithms Group. The algorithms group, headed by prof. Mark de Berg, performs fundamental research in computational geometry, I/O-efficient algorithms, and FPT and graph algorithms, with applications to, for instance, geographic information systems. Currently the group consists of Mark de Berg, Kevin Buchin, Herman Haverkort, and Bart Jansen, and several PhD students. Hans Bodlaender (Utrecht University) is associated to the group as a part-time professor.

The TU Eindhoven and the Faculty of Mathematics and Computer Science. The TU Eindhoven (TU/e) was established in 1956 as a polytechnic. It has grown into a university with nine faculties. The TU/e now has approximately 3000 employees (incl. PhD students) and 8000 BSc and MSc students. The Department of Computer Science offers several bachelor and master programs, all of which are taught in English. It has eight well-established research groups, one of which is the Algorithms Group. The TU/e campus is in the center of Eindhoven. The city of Eindhoven is located in the south of the Netherlands. It is a lively city with about 200,000 inhabitants, making it the fifth largest city of the Netherlands. Including suburbs the population is about 400,000.

Being a PhD student in the Netherlands. In the Netherlands, every PhD student gets paid a salary; no additional grants are needed. Moreover, although PhD students sometimes take courses, there is no minimum requirement. Hence, PhD students are more like employees than like students. Indeed, the Dutch word for PhD student translates to "research trainee". The work of a PhD student may include assisting in courses of BSc or MSc programs of the department. This amounts to at most 20% of the time; the remaining time is spent on research and research-related activities. Foreign PhD students need not speak Dutch: it is easy to get by with English, not only at the university but also in everyday life.

We offer.

* A full-time temporary appointment for a period of 4 years, with an intermediate evaluation after 9 months;
* A gross salary of € 2,125 per month in the first year increasing up to € 2,717 per month in the fourth year;
* Support for your personal development and career planning including courses, summer schools, conference visits etc.;
* A research position in an enthusiastic and internationally renowned research group;
* A broad package of fringe benefits (e.g. excellent technical infrastructure, child daycare, savings schemes and excellent sport facilities).


More information. If you want to know more about the project, please contact Mark de Berg (mdberg@win.tue.nl) or Hans Bodlaender (h.l.bodlaender@tue.nl)

How to apply. Applications must be done through the Networks website:

http://www.thenetworkcenter.nl/Open-Positions/openposition/9/PhD-position-FPT-algorithms-for-geometric-network-problems-TU-Eindhoven-


**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************