Bringing approximation algorithms for throughput maximization to the next level

• Applicant: Professor Dr. Andreas Wiese
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 551896423

Combinatorial optimization is a branch of theoretical computer science that deals with finding the best solution from a discrete set of possibilities. It studies problems with applications in various settings like scheduling, logistics, and network optimization. In particular, combinatorial optimization can be applied to use limited resources optimally. One important aspect of this is to optimize the throughput in a given system. One example of this are machines in a factory that are used for producing goods, e.g., in a just-in-time production system. Buying new machines is expensive; therefore, it is important to utilize the existing machines optimally. Recently, there has been tremendous progress in an important throughput maximization problem, the Un-splittable Flow on a Path problem (UFP). This problem models selecting jobs with fixed execution time intervals on a single machine while the jobs share a common limited resource, e.g., energy, transmission bandwidth, or workers. The goal is to select the most profitable set of jobs that the given resource can support. By now, we have a very good understanding of UFP, and we know the best possible approximation ratio for it, particularly due to the results of this project's principal investigator (PI) and his co-authors. However, our understanding falls short in the natural settings in which there is a time window for each job, the generalization in which the jobs are partitioned into groups (bags) such that we can select only one job per bag, if there are several machines, or if there are several resources. This project aims to significantly extend our understanding of throughput maximization in these more general cases. Ideally, we want to understand them equally well as the classical setting in which there is only one machine, one resource, and no time windows or bags. Since our studied problems are NP-hard, we want to develop approximation algorithms for them, i.e., efficient (i.e., polynomial time) algorithms that always compute a solution that is provably close to the optimal solution. Also, we want to establish complementary complexity results showing the limits of efficient algorithms in these settings, e.g., by proving that certain approximation ratios cannot be achieved (under standard complexity-theoretic assumptions).

• DFG Programme: Research Grants
• International Connection: Switzerland
• Cooperation Partner: Professor Fabrizio Grandoni