A linear algorithm for integer programming in the plane

• 成果类型: Article
• 署名作者: Eisenbrand, F; Laue, S
• 署名单位: Max Planck Society
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0520-0
• 发表日期: 2005
• 页码: 249-259
• 关键词: production sets; indivisibilities; dimension; time

摘要

We show that a 2-variable integer program, defined by m constraints involving coefficients with at most phi bits, can be solved with O(m + phi) arithmetic operations on rational numbers of size O(phi).