Faculties / Central Institutes
Funding
Project heads
Martin Skutella and Philipp Warode
Project member
Srinwanti Debgupta
Project duration
01.07.2025 - 30.06.2028
This research project focuses on unsplittable flows, a fundamental concept in network optimization. In many real-world systems, such as transportation, logistics, and communication networks, it is often necessary to route a commodity along a single path rather than splitting it across multiple paths.
While classical network flow models allow splitting, unsplittable flows introduce additional constraints that significantly increase computational complexity. Understanding these challenges is essential for designing efficient and reliable routing systems.
Many unsplittable flow problems are NP-complete, meaning that no efficient solution methods are known for all cases.
The project aims to improve both the theoretical understanding and algorithmic solutions of unsplittable flow problems. A central challenge is transforming a fractional flow (where splitting is allowed) into an unsplittable one while controlling deviations.
One key bound studied in the project is:
$\displaystyle y_a \leq x_a + d_{\max}$
where $x_a$ is the original (fractional) flow on arc $a$, $y_a$ is the unsplittable flow, and $d_{\max}$ is the maximum demand. This inequality ensures that congestion remains controlled.
Investigates when flows can be routed integrally (without splitting) based on structural properties of the network. A central concept is the cut condition, which compares network capacity with demand across partitions.
Extends the model to multiple sources and sinks. Each source-sink pair must still use a single path, but routing is more flexible overall. The goal is to design efficient approximation algorithms for:
Develops new techniques to iteratively improve routing solutions by modifying paths. These methods aim to be more flexible and practical than classical approaches, with promising empirical performance.
