Academic Journal
ALL LINEAR AND INTEGER PROGRAMS ARE SLIM 3-WAY TRANSPORTATION PROGRAMS
| العنوان: | ALL LINEAR AND INTEGER PROGRAMS ARE SLIM 3-WAY TRANSPORTATION PROGRAMS |
|---|---|
| المؤلفون: | Jesús A. De Loera, Shmuel Onn |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://ie.technion.ac.il/~onn/Selected/SIAMJO06.pdf. |
| سنة النشر: | 2006 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | tables, multiway table, statistical table, data security, privacy, approximation algorithms, Markov |
| الوصف: | We show that any rational convex polytope is polynomial-time representable as a 3-way line-sum transportation polytope of “slim” (r, c, 3) format. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure. We provide a polynomial-time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bitransportation programs. Our construction resolves several standing problems on 3-way transportation polytopes. For example, it demonstrates that, unlike the case of 2-way contingency tables, the range of values an entry can attain in any slim 3-way contingency table with specified 2-margins can contain arbitrary gaps. Our smallest such example has format (6, 4, 3). Our construction provides a powerful automatic tool for studying concrete questions about transportation polytopes and contingency tables. For example, it automatically provides new proofs for some classical results, including a well-known “real-feasible but integer-infeasible” (6, 4, 3)-transportation polytope of M. Vlach, and bitransportation programs where any feasible bitransportation must have an arbitrarily large prescribed denominator. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.3154; http://ie.technion.ac.il/~onn/Selected/SIAMJO06.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.3154 http://ie.technion.ac.il/~onn/Selected/SIAMJO06.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.5640DF71 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |