Structural results for integer linear programs

点击翻译按钮获取中文摘要

The main focus of this project is the design of efficient algorithms and structural results for so-called integer linear programs (ILPs). This very general form of optimization problems have many applications in the field of combinatorial optimization. Clearly, a more efficient algorithm for solving ILPs would have implications in many areas of theoretical computer science. More precise knowledge of the structure of solutions of ILPs leads to immediate algorithmic applications in which the properties of a solution can be used to limit the search for an optimum solution. We believe that structural results about solutions of ILPs can serve as a universal tool for the design of efficient algorithms - both directly for ILPs and for many applications of them. At the same time, we want to improve known algorithms with regard to their running time and to prove lower bounds on the running time of algorithms based on well known complexity assumptions such as the exponential time hypothesis (ETH), an assumption on the runtime of algorithms for solving the satisfiability problem (SAT).