Sparse Integer Programming Is Fixed-Parameter Tractable

• 成果类型: Article
• 署名作者: Eisenbrand, Friedrich; Hunkenschroeder, Christoph; Klein, Kim-Manuel; Koutecky, Martin; Levin, Asaf; Onn, Shmuel
• 署名单位: Technical University of Berlin; University of Lubeck; Charles University Prague; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0162
• 发表日期: 2025
• 关键词: Complexity; THEOREMS

摘要

We study the general integer programming problem where the number of variables n is a variable part of the input. We consider two natural parameters of the constraint matrix A: its numeric measure a and its sparsity measure d. We present an algorithm for solving integer programming in time g(a,d)poly(n,L), where g is some computable function of the parameters a and d, and L is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by a and d, and is solvable in polynomial time for every fixed a and d. Our results also extend to nonlinear separable convex objective functions.