Huge multiway table problems

DOI10.1016/J.DISOPT.2014.07.003MaRDI QIDQ2339833zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 9 April 2015

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.1189

zbMATH Keywords

integer programmingGraver basismultiway tableinteger cone

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Abstract: Deciding the existence of an $limesmimesn$ integer threeway table with given line-sums is NP-complete already for fixed $l=3$, but is in P with both $l,m$ fixed. Here we consider {em huge} tables, where the variable dimension $n$ is encoded in {em binary}. Combining recent results on integer cones and Graver bases, we show that if the number of {em layer types} is fixed, then the problem is in P, whereas if it is variable, then the problem is in NP intersect coNP. Our treatment goes through the more general class of $n$-fold integer programming problems.

Recommendations

• Huge unimodular \(n\)-fold programs
• \(N\)-fold integer programming
• The Complexity of Three-Way Statistical Tables
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• Theory and Applications of n-Fold Integer Programming

Cites work

• A finiteness theorem for Markov bases of hierarchical models
• A polynomial oracle-time algorithm for convex integer minimization
• A polynomial-time algorithm for optimizing over \(N\)-fold 4-block decomposable integer programs
• All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
• Carathéodory bounds for integer cones
• Higher Lawrence configurations.
• Integer Programming with a Fixed Number of Variables
• Minimal Basis for a Connected Markov Chain over 3 x 3 x K Contingency Tables with Fixed Two-Dimensional Marginals
• Nonlinear discrete optimization. An algorithmic theory
• \(N\)-fold integer programming
• \(n\)-fold integer programming in cubic time

Cited in

(8)

• Combinatorial \(n\)-fold integer programming and applications
• \(N\)-fold integer programming
• High-multiplicity \(N\)-fold IP via configuration LP
• The Complexity of Three-Way Statistical Tables
• Parameterized complexity of configuration integer programs
• Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
• Huge unimodular \(n\)-fold programs
• Combinatorial \(n\)-fold integer programming and applications

This page was built for publication: Huge multiway table problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339833)