Scholarlink

<p>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 &amp; Yuditsky (J. ACM 72(1), 1-50 (2025)) by allowing for additional, unifying constraints and variables. Further, we give a randomized polynomial-time algorithm for the natural transposed case, i.e., where the main part of the matrix has two non-zeros per column instead of per row.</p>

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

Totally \(\Delta \)-modular IPs with two non-zeros in most rows

  • 期刊论文

  • 发表日期：

    2026年6月22日

查看全文
  • 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. Further, we give a randomized polynomial-time algorithm for the natural transposed case, i.e., where the main part of the matrix has two non-zeros per column instead of per row.