Approximation Methods in Integer Programming

• Applicant: Professor Dr.-Ing. Kim-Manuel Klein
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 445520385

The primary objective of this project is to develop novel techniques for designing approximation algorithms for packing and scheduling problems based on a structural understanding. Instead of rounding input instances as in conventional approaches, we aim to adapt ILP algorithms to operate with original (unrounded) item sizes. For this, fundamentally new mathematical structural theorems regarding the form and existence of approximate solutions are needed. Utilizing these new methods, we aim to achieve two main goals: Firstly, we intend to develop so called additive approximation schemes for fundamental packing and scheduling problems, such as the knapsack problem and the makespan scheduling problem. An additive approximation scheme provides a performance guarantee of the form OPT + \epsilon a, where a is a problem-specific parameter - for instance, the maximum item size. Given that typically a << OPT, this performance guarantee offers advantages over classical approximation schemes with a guarantee of (1 + \epsilon)OPT. As part of this project, we seek to discover fundamental techniques and insights to develop approximation algorithms of this form. Interesting connections to the field of parameterized complexity for scheduling and packing problems emerge from this approach. Secondly, we aim to address known open questions in the domain of flow-time scheduling by leveraging our novel approach.

• DFG Programme: Research Grants