The Complexity of Three-Way Statistical Tables
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 33 (4), 819-836
- https://doi.org/10.1137/s0097539702403803
Abstract
Multiway tables with specified marginals arise in a variety of applications in statistics and operations research. We provide a comprehensive complexity classification of three fundamental computational problems on tables: existence, counting, and entry-security.One outcome of our work is that each of the following problems is intractable already for "slim" 3-tables, with constant number 3 of rows: (1) deciding existence of 3-tables with specified 2-marginals; (2) counting all 3-tables with specified 2-marginals; (3) deciding whether a specified value is attained in a specified entry by at least one of the 3-tables having the same 2-marginals as a given table. This implies that a characterization of feasible marginals for such slim tables, sought by much recent research, is unlikely to exist.Another consequence of our study is a systematic efficient way of embedding the set of 3-tables satisfying any given 1-marginals and entry upper bounds in a set of slim 3-tables satisfying suitable 2-marginals with no entry bounds. This provides a valuable tool for studying multi-index transportation problems and multi-index transportation polytopes. Remarkably, it enables us to automatically recover a famous example due to Vlach of a "real-feasible integer-infeasible" collection of 2-marginals for 3-tables of smallest possible size (3,4,6).Keywords
This publication has 15 references indexed in Scilit:
- Algebraic unimodular countingMathematical Programming, 2003
- Gröbner Bases and Polyhedral Geometry of Reducible and Cyclic ModelsJournal of Combinatorial Theory, Series A, 2002
- Momentopes, the Complexity of Vector Partitioning, and Davenport—Schinzel SequencesDiscrete & Computational Geometry, 2002
- The magnitude distribution of declustered earthquakes in Southern CaliforniaProceedings of the National Academy of Sciences of the United States of America, 2000
- Separable partitionsDiscrete Applied Mathematics, 1999
- A Polynomial Time Algorithm for Shaped Partition ProblemsSIAM Journal on Optimization, 1999
- Sampling contingency tablesRandom Structures & Algorithms, 1997
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is FixedMathematics of Operations Research, 1994
- A Graph Theoretic Approach to Statistical Data SecuritySIAM Journal on Computing, 1988
- Testing for Independence in a Two-Way Table: New Interpretations of the Chi-Square StatisticThe Annals of Statistics, 1985