2 PhD positions in Combinatorial Optimization
2 PhD positions in Combinatorial Optimization
You cannot apply for this job anymore (deadline was 3 Jun 2018).
Browse the current job offers or choose an item in the top navigation above.
Job description
The group Combinatorial Optimization is one of three groups that jointly form the section Discrete Mathematics (DM); the other two groups are Coding Theory and Cryptography, and Discrete Algebra and Geometry. The section DM is one of the three sections within Mathematics of the Department of Mathematics and Computer Science.
The research program in Combinatorial Optimization studies discrete optimization problems. More specifically, we investigate the structure of such problems, analyze the relations between different problems, and use this knowledge to design efficient and effective algorithms for solving them. We study both exact and heuristic algorithms. We are also interested in combinatorial optimization problems where the input is revealed only gradually, or where there is uncertainty in the parameters, leading to online, stochastic or robust solution methods. We develop theoretic results, for instance in graph theory, parameterized complexity and matroids, and apply these to real-world situations. Typical application areas are scheduling, production planning, logistics, network design, communication and routing in networks, and health care. The group actively explores new research lines in Data Science and maintains strong ties with industry.
The Combinatorial Optimization group has openings for two PhD students (for a period of four years). The candidates will work on two different projects. One project is called 'Fine-grained (Parameterized) Complexity of Hard Problems', and will be supervised by Dr. Jesper Nederlof, the other project is called 'Sport Scheduling', and will be supervised by Prof.Dr. Frits Spieksma.
Fine-grained (Parameterized) Complexity of Hard Problems
Our main goal is to improve the understanding of the exact complexity of basic (NP-)hard problems such as the Travelling Salesman, Set Cover or Subset Sum problem. In particular, the project aims to study for which classes of instances various elementary algorithms can be improved. A particular emphasis of the project herein is to rigorously investigate the power of standard decomposition methods such as Branching, Dynamic Programming, and Meet-in-the-Middle via parameters of appropriate matrices.
While the project will mainly touch the fields of Parameterized Complexity and Fine-Grained Complexity, the project is also likely to touch other subfields of Theoretical Computer Science including Communication Complexity and Approximation Algorithms; but the direction may vary depending on the candidate's preferences.
Sport Scheduling
The increasing relevance of sport in today's society is undisputed. Millions of people, all over the world, are enthralled by contests where athletes compete against each other, both as individuals or in a team format. Such events form a source of inspiration for young generations. At the same time, almost every sports competition needs a schedule, stating who will play whom, when, and where. A good schedule is important, because it has an effect on the outcome of the competition, public attendance, commercial interests, and even the health of the players.
Our main goal is to construct models for problems in sport scheduling, and to develop efficient methods for solving these models. Perhaps surprisingly, many mathematical questions with respect to, for instance, round-robin tournaments, have not yet been answered satisfactorily. Questions concerning necessary and sufficient conditions about so-called Home-Away Pattern sets have remained open. In addition, the use of good schedules in practice, both on a professional level as well as in amateur leagues is not as developed as one would hope. It is the goal of this research project to fill this gap, and to contribute both theoretical results in sports scheduling, as to have an impact on practice.
The research program in Combinatorial Optimization studies discrete optimization problems. More specifically, we investigate the structure of such problems, analyze the relations between different problems, and use this knowledge to design efficient and effective algorithms for solving them. We study both exact and heuristic algorithms. We are also interested in combinatorial optimization problems where the input is revealed only gradually, or where there is uncertainty in the parameters, leading to online, stochastic or robust solution methods. We develop theoretic results, for instance in graph theory, parameterized complexity and matroids, and apply these to real-world situations. Typical application areas are scheduling, production planning, logistics, network design, communication and routing in networks, and health care. The group actively explores new research lines in Data Science and maintains strong ties with industry.
The Combinatorial Optimization group has openings for two PhD students (for a period of four years). The candidates will work on two different projects. One project is called 'Fine-grained (Parameterized) Complexity of Hard Problems', and will be supervised by Dr. Jesper Nederlof, the other project is called 'Sport Scheduling', and will be supervised by Prof.Dr. Frits Spieksma.
Fine-grained (Parameterized) Complexity of Hard Problems
Our main goal is to improve the understanding of the exact complexity of basic (NP-)hard problems such as the Travelling Salesman, Set Cover or Subset Sum problem. In particular, the project aims to study for which classes of instances various elementary algorithms can be improved. A particular emphasis of the project herein is to rigorously investigate the power of standard decomposition methods such as Branching, Dynamic Programming, and Meet-in-the-Middle via parameters of appropriate matrices.
While the project will mainly touch the fields of Parameterized Complexity and Fine-Grained Complexity, the project is also likely to touch other subfields of Theoretical Computer Science including Communication Complexity and Approximation Algorithms; but the direction may vary depending on the candidate's preferences.
Sport Scheduling
The increasing relevance of sport in today's society is undisputed. Millions of people, all over the world, are enthralled by contests where athletes compete against each other, both as individuals or in a team format. Such events form a source of inspiration for young generations. At the same time, almost every sports competition needs a schedule, stating who will play whom, when, and where. A good schedule is important, because it has an effect on the outcome of the competition, public attendance, commercial interests, and even the health of the players.
Our main goal is to construct models for problems in sport scheduling, and to develop efficient methods for solving these models. Perhaps surprisingly, many mathematical questions with respect to, for instance, round-robin tournaments, have not yet been answered satisfactorily. Questions concerning necessary and sufficient conditions about so-called Home-Away Pattern sets have remained open. In addition, the use of good schedules in practice, both on a professional level as well as in amateur leagues is not as developed as one would hope. It is the goal of this research project to fill this gap, and to contribute both theoretical results in sports scheduling, as to have an impact on practice.
Specifications
- max. 38 hours per week
- Eindhoven View on Google Maps
:fill(white)/logos/tue-en-wide_acOLN2b.png)
Eindhoven University of Technology (TU/e)
Requirements
You have successfully completed a master's degree in mathematics, computer science, or a related discipline. You have a sound understanding of mathematical (in particular combinatorial) optimization and/or theoretical computer science. In addition, you are inquisitive, analytically talented, and preferably equipped with implementation skills. Creativity and team spirit are also very welcome.
Conditions of employment
We offer:A challenging job for 4 years in a dynamic and ambitious university and a stimulating research environment; Support with your professional and personal development; A gross salary per month of € 2222,- (first year) as a PhD up to € 2840,- (final year) in accordance with the Collective Labor Agreement of the Dutch Universities 8% holiday allowance 8.3% end of the year allowance. An extensive package of fringe benefits (e.g. support in moving expenses, excellent technical infrastructure, on-campus child care, and excellent sports facilities.
