Scholarlink

Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 72(1), 1–50 (2025)) by allowing for additional, unifying constraints and variables.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Totally \(\varDelta \) -Modular IPs with Two Non-zeros in Most Rows

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Stefan Kober

摘要

Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve IPs where the constraint matrix has bounded subdeterminants and at most two non-zeros per row after removing a constant number of rows and columns. This result extends the work by Fiorini, Joret, Weltge & Yuditsky (J. ACM 72(1), 1–50 (2025)) by allowing for additional, unifying constraints and variables.