Structural results for integer linear programs

这个项目的主要焦点是设计所谓的整数线性规划(ILPS)的有效算法和结构结果。这种非常一般形式的优化问题在组合优化领域有许多应用。显然，一种更有效的求解ILPS的算法将在理论计算机科学的许多领域产生影响。对ILPS解的结构的更精确的了解导致了直接的算法应用，其中解的性质可以用来限制对最优解的搜索。我们相信，关于ILPS解的结构结果可以作为设计高效算法的通用工具--无论是直接用于ILPS还是对于它们的许多应用。同时，我们希望改进已知算法的运行时间，并基于众所周知的复杂性假设，如指数时间假设(ETH)，证明算法运行时间的下界。ETH是关于求解可满足性问题(SAT)的算法的运行时间假设。

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).