Huge multiway table problems

DOI10.1016/J.DISOPT.2014.07.003zbMATH Open1308.90108arXiv1405.1189OpenAlexW2042842265MaRDI QIDQ2339833FDOQ2339833

Shmuel Onn

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

integer programmingGraver basismultiway tableinteger cone

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Huge Unimodular $n$-Fold Programs
• High-multiplicity \(N\)-fold IP via configuration LP
• The Complexity of Three-Way Statistical Tables
• Parameterized complexity of configuration integer programs
• Title not available (Why is that?)
• 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)