Structural Parameters in Integer Programming

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

In the context of this project, we consider integer linear programs (ILPs) of the form {x \in Z^n | Ax = b, x >= 0}. Most classical algorithmic problems can be easily formulated as such an ILP - for example, the classical subset sum problem or the bin packing problem. Depending on the formulated problem, the corresponding ILP usually has a very special shape. The main goal of the project is to characterize this structure and to develop a better understanding of it and its geometric properties. Building on a geometric interpretation of these ILPs, we would then like to develop algorithms for solving the ILPs and thus find more efficient algorithms for several fundamental algorithmic problems. An important goal of the proposal is to develop an algorithm for solving ILPs with a running time of f(\Delta) poly(|I|), where \Delta is the absolute value of the largest subdeterminate of the constraint matrix. Our approach is based on a dichotomy statement of feasibility ILPs, which we would also like to study in more detail.

• DFG Programme: Research Grants