The Complexity of Three-Way Statistical Tables
| dc.creator | De Loera, Jesus | |
| dc.creator | Onn, Shmuel | |
| dc.date | 2002-07-22 | |
| dc.date.accessioned | 2026-07-07T07:53:03Z | |
| dc.date.available | 2026-07-07T07:53:03Z | |
| dc.description | Multi-way 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 major outcome of our work is that each of the following problems is intractable already for "slim" 3-tables, with constant and smallest possible number 3 of rows: (1) deciding existence of 3-tables with given consistent 2-marginals; (2) counting all 3-tables with given 2-marginals; (3) finding whether an integer value is attained in entry (i,j,k) by at least one of the 3-tables satisfying given (feasible) 2-marginals. This implies that a characterization of feasible marginals for such slim tables, sought by much recent research, is unlikely to exist. Another important 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. | |
| dc.identifier | https://arxiv.org/abs/math/0207200 | |
| dc.identifier | http://arxiv.org/abs/math/0207200 | |
| dc.identifier | SIAM Journal on Computing, 33:819--836, 2004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/126106 | |
| dc.subject | Combinatorics | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Optimization and Control | |
| dc.title | The Complexity of Three-Way Statistical Tables | |
| dc.type | text |