Betreuer

Daniel Vaz

General Information

• The seminar is planned for Thursdays in the afternoon, and will be in-person when posssible.
• The first session is June 2nd, with two 45-minute talks per session.
• Send an ordered list of your preferred topics (at least 5!) to Daniel until April 3rd.
• If you would prefer a topic not on the list or have a different suggestion, let us know.

Topics

Topic 1: Shortest Path in Road Networks

Computing shortest paths is one of the most fundamental problems in combinatorial optimization and finds many applications, such as finding the fastest route between two points on a map.

When computing the route between faraway points in a maps application, even the best classical algorithms can take longer than required (~1s).

For this seminar topic, we look at one approach that vastly improves the time required for shortest path queries (to <2ms), while maintaining the flexibility that is required for practical applications. This approach uses combinatorial optimization and graph theoretical tools to achieve its results, and has been used for both Bing and Apple maps.

Topic 2: Kidney Exchange

Kidney transplants are the most common form of transplant done worldwide, accounting for around 90 000 transplants annually. The vast majority of the donor kidneys come from deceased donors, as living donors are harder to find and the transplants harder to organize. However, the number of deceased donors is not sufficient to cover the necessary number of donor kidneys, and thus methods for facilitating living donation have been researched.

One increasingly common method for living donor kidney transplants is to organize kidney exchanges, where two patients, each with their incompatible donor (family or friend) are paired, so that both patients receive a kidney from the family or friend of the other patient. These kidney exchanges can be extended to form larger cycles, or even chains started by an altruistic donor (not associated with any patient). These longer chains and cycles allow for greater flexibility, and thus to obtain a larger number of transplants.

The paper for this topic presents algorithms that use integer programming to optimize the chains and cycles for kidney exchange, with the goal of obtaining better solutions, which are used to organize actual kidney exchanges in US hospitals.

Topic 3: Public Transport I

Public transport is a crucial tool for mobility in cities, providing a way to tackle traffic jams, move large amounts of people, and tackle climate change. However, planning a well-functioning public transport system is a complex and multi-faceted task.

For this topic, we study the case of Netherlands Railways, and learn about the diverse planning tasks and challenges involved in the functioning of such a system. We then look at one of these tasks more deeply and the algorithms that were used to solve the corresponding combinatorial problems.

Specifically, we look at the problem of scheduling trains taking into account the natural variation present in trip times, using a mixed integer program that takes the necessary requirements into account.

Topic 4: Public Transport II

Although public transport networks can offer many benefits, they also bring with them their own challenges. For example, it can be difficult for a user to find the fastest way to go to their desired destination.

This topic concerns the algorithms to do so, that is, the problem of finding the shortest path between two points in a timetabled system, with the option to specify the number of transfers. The approach that we study is tailored to this specific problem, and so manages to be simpler and faster than Dijkstra-based approaches.

Topic 5: Multiple Sequence Alignment (Genome reconstruction)

Multiple sequence alignment (MSA) is the problem of aligning and finding similarities between three or more biological sequences, such as proteins or genetic material (DNA or RNA). These methods are used to analyze biological data to determine how close a set of sequences is to each other, either to confirm hypotheses of common evolutionary ancestry or find out in which way the input sequences are related and where differences exist.

Given the length of genetic sequences (human DNA has around 3 billion bases), efficient algorithms are important to obtain useful results quickly. In this topic, we look at one algorithm for multiple sequence alignment that is fast in practice and provides a solution of good quality, using fast algorithms for string matching, adjusted for this specific problem.

Topic 6: Phylogenetic Tree Reconstruction

A phylogenetic tree is a mathematical representation of the evolutionary history of a group of species. While we cannot truly know exactly how a species emerged, we can use the genetic data that we have today to estimate how species can be related, as well as whether other species existed that stood as common ancestors for species that exist today. Phylogenetic tree reconstruction is the problem of reconstructing the phylogenetic tree as best as we can, using genetic data or other data available today.

For this topic, we will take a look at this problem from a theoretical point of view, and look at an algorithm that has a better asymptotic running time than previously thought possible. The techniques considered use advanced data structures and other algorithmic techniques.

Topic 7: Jamming in Wireless Networks

In network systems, and in particular in wireless networks, jamming can be a problem, since an adversary can broadcast noise to overwhelm the frequency bands used for communication, thus making communication impossible. Though there is little that can be done against a powerful jammer, these tend to use large amounts of energy and thus are impractical for long periods of time. Communication protocols can use this knowledge to ensure that communication is resilient against a reasonable threat of jamming.

In this topic, we look at the popular Wi-Fi (IEEE 802.11) protocols, and specifically at the media access control protocols, which are used to manage wireless communication. We then study how this protocol reacts to noise and jamming, and how easy it is to block communications using these methods. Finally, we look at alternative protocols, which could improve the performance of wireless networks under jamming.

Topic 8: Electoral District Design

In many elections, both in Germany and abroad, voting takes place across different election districts. As representatives are usually directly elected by each district, the choice of district lines can have a major influence on election results, as e.g. can be seen with the so called gerrymandering. District borders are usually chosen in some semi-manual process, though we will see that one can formulate these complex decisions as optimization problems and achieve "better" results.
This topic will present the mathematical theory behind electoral district design and examine structural and algorithmic approaches from both combinatorial and LP/MIP directions.

Topic 9: Traveling SalesPerson

The Traveling Salesperson Problem (TSP) is one of the most well studied problems in combinatorial optimizations. While there is a wealth of algorithmic and complexity results from the theoretical point of view, the approaches used in practice are usually quite different.  Thus, even though the problem is NP-hard, there are instances with around 50000 vertices that have been solved to optimality.
This topic will explore the heuristics commonly used for solving TSP instances and show examples of relevant TSP applications.

Topic 10: Advertisement Selection

Serving advertisements to visitors on a website is a highly dynamic problem. In a typical setting, there are visitors with some known perferences arriving in an online fashion on some webpage, which then has to decide what kind of advertisements to display. Advertisers want their ads to only be served to relevant customers and their budgetary constraints to be fulfilled, while the advertisement algorithm tries to maximize the achieved revenue. This tricky balance between different requirements has produced a wealth of research results over the past two decades.
The typical approaches are combinatorial, with some influences from LP theory and game theory.

Topic 11: Scheduling

Scheduling is one of the most diverse areas of applied optimization. With topics ranging from simple single machine scheduling to complex flow-shop type settings, the range of used techniques is equally large. In this topic we want to look at recent results for scheduling jobs on complex systems consisting of several related machines. These types of optimization problems are directly inspired by applications from industry. The techniques used will focus on LP type bounds combined with some simpler combinatorial arguments.

Topic 12: Operation Room Scheduling

Finding suitable schedules for operation rooms (ORs) in hospitals is an important task, as good schedules can both maximize patient satisfaction while simultaneously ensuring a large patient throughput. Determining feasible schedules can be difficult though, as there are a multitude of constraints such as mandatory breaks for surgeons and maximal working times. The problem setting is also often viewed from a stochastic and online perspective, as both operation times are not fixed and often there is a need to accommodate urgent surgeries on a short notice and patients might miss their assignments.
This topic will explore different OR scheduling scenarios and examine solution approaches both from MIP and more combinatorial viewpoints.