Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory

详细信息    查看全文

• 作者：Shmuel Onn ^{onn@ie.technion.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Integer programming ; Integer Carath&eacute ; odory ; Multiway table ; Bin packing ; Cutting stock ; Fixed-parameter tractable ; Totally unimodular ; Multicommodity flow
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：83
• 期：1
• 页码：207-214
• 全文大小：296 K

文摘

The three-way table problem is to decide if there exists an l×m×n$l\times m\times n$ table satisfying given line sums, and find a table if yes. Recently, it was shown to be fixed-parameter tractable with parameters l,m$l,m$. Here we extend this and show that the huge version of the problem, where the variable side n   is encoded in binary, is also fixed-parameter tractable with parameters l,m$l,m$. We also conclude that the huge multicommodity flow problem with a huge number of consumers is fixed-parameter tractable. One of our tools is a theorem about unimodular monoids which is of interest on its own right.