Approximation Methods in Integer Programming

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

The main goal of this project is to develop new universal methods and techniques to solve integer linear programs (ILPs) approximately. Motivated by new developments in the area, it is our approach to use an augmentation framwork where we stepwise improve upon an existing feasible solution by specifically structured augmentation elements.We consider classes of ILPs which originate from the formulation of concrete algorithmic problems like the classical bin packing problem or the scheduling problem on heterogeneous machines. For these problems there are long standing open problems concerning their approximability. Our goal is to make progress in these open questions with our novel approach.As a second goal of this project, we want to develop new algorihtms and analyzing tools for online algorithms using methods and views from the area of (integer) linear programming.We consider an online ILP where the right hand side vector changes over time. This online ILP generalizes several known online problems like the classical online bin packing problem. Our approach do determine the (asymptotic) competitive ratio of the online ILP relies on a powerful geometric interpretation. In the end, we hope to develop algorithms that improve upon the competitive ratio of existing algorithms.

• DFG Programme: Research Grants