Student projects
For students with a deep interest in optimization, and that have attended the appropriate courses, a project thesis in optimization is an excellent opportunity to acquire a deeper knowledge on the topic. This page gives an overview about:
- The different project types, and the corresponding requirements
- The project outcomes (written report and presentation)
- The application procedure
- The project topics
Also, please note that we often get more requests than what we can handle. Hence, we apologize in advance if we cannot supervise your student project.
Project types and requirements
In addition to the protected page requirements by D-MATH, the table below shows what courses we expect student to have successfully finished before writing a thesis in the group of Prof. Zenklusen.
Project Type | Level | Requirements |
|---|---|---|
| Bachelor's thesis | Bachelor students |
|
| Semester paper | Master students |
|
| Master's thesis | Master students |
|
Specialized Optimization courses include
- Advanced Topics in Discrete Optimization
- Network and Integer Optimization
- Convex Optimization
In exceptional cases, other courses may qualify as specialized courses. Please discuss this with the study advisor.
Project outcomes
At the end of the project, students are required to hand in a written report and give a presentation. The presentation should last at most 30 minutes (make sure not to exceed this time) plus time for questions and answers.
Some hints and guidelines for composing the written report and the final presentation can be found in Download our tutorial (PDF, 3.4 MB) and on the D-MATH website.
Application procedure
Before you apply, please check the list of eligible supervisors for your respective thesis and degree program.
In order to apply for a Bachelor's thesis, a semester paper, or a Master's thesis, write an e-mail to the study advisor with the following information:
- Your name
- Your study program
- Your current state of studies
- What type of project you are interested in (Bachelor's thesis/semester paper/Master's thesis)
- When you'd like to work on the project
- The courses that you have attended at IFOR (and other relevant courses)
- Whether you are more interested in a theoretically or practically inclined project
The study advisor should be contacted a few months before the desired start of the project.
Project topics
The topics we offer are typically aligned with current research thrusts/projects in the group, and thus change over time.
To give you an idea of some prior topics, hereafter we list some abstracts of theses completed in the Zenklusen Group in recent years.
Martin Nägele: Refuting a Conjecture of Goemans on Minimum Degree-Bounded Spanning Trees
In the degree-bounded spanning tree problem, we are given an undirected graph with edge costs and a degree bound for every vertex. The task is to find a spanning tree T whose degree at each vertex does not exceed the degree bound and T is of minimum cost among all such spanning trees. Even checking whether a feasible spanning tree exists is well known to be NP-hard. Thus, interest surged in understanding whether a small violation of the degree constraints may make it possible to efficiently obtain a spanning tree whose cost is not larger than the optimum spanning tree, which does not violate the degree constraints. In 2006, Goemans presented a nearly optimal algorithm, based on matroid intersection, which leads to a degree violation of at most 2 units. In 2007, Singh and Lau closed the gap by showing that iterative relaxation allows for obtaining the same result with degree violation of at most 1. Besides iterative relaxation, no other technique is known to lead to the same result. Interestingly, Goemans stated a conjecture which, if true, would imply that his matroid intersection approach would as well lead to a violation of at most 1 unit. In this work, we refute Goemans' conjecture, by refuting an even weaker version of it.
Simon Bruggmann: On the single-source unsplittable flow problem with costs
In the single-source unsplittable flow problem, we are given a directed graph whose arcs are assigned a capacity and a cost. There are a number of commodities with associated demands and terminals, and the task is to route all commodities simultaneously from a common source vertex to the given terminals such that the demand of each commodity is routed along a single path.
Dinitz, Garg, and Goemans (1999) showed that any flow f that is allowed to split the commodities can be transformed into an unsplittable flow funsp which has the property that for every arc a, funsp(a) exceeds f (a) by less than the maximum demand routed along a by the unsplittable flow funsp. Goemans conjectured that their result extends in the way that for each splittable flow f, there exists an unsplittable flow funsp which has the property above and which is at most as expensive as f.
We show that the conjecture holds for two special cases. For the first case, where we require the given graph to be 2-layered, we present an algorithm that is based on iterative relaxation and proves the conjecture in this context. The second case for which we prove the conjecture is the situation in which all demands are equal except for one which may be bigger. In particular, this yields an affirmative answer to the conjecture for the case where there are only two commodities.