On Integer Programming, Discrepancy, and Convolution

• 成果类型: Article
• 署名作者: Jansen, Klaus; Rohwedder, Lars
• 署名单位: University of Kiel; Maastricht University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1308
• 发表日期: 2023
• 页码: 1481-1495
• 关键词: linear-time; algorithms; dimension

摘要

Integer programs with a fixed number of constraints are solvable in pseudo-polynomial time in the largest coefficient of any constraint. We give a new algorithm which improves the running time of the state of the art. Moreover, we show that improving on our algorithm for any number of constraints is equivalent to improving over the quadratic time algorithm for (min, +)-convolution. This is strong evidence that our algorithm's running time is the best possible. We also present a specialized algorithm for testing the feasibility of an integer program and give a tight lower bound, which is based on the strong exponential time hypothesis in this case.