×

zbMATH — the first resource for mathematics

Compressed polytopes and statistical disclosure limitation. (English) Zbl 1121.52028
A lattice polytope \(P\) is said to be compressed if every pulling triangulation of it (using only lattice points from \(P\)) is unimodular. (An example is the Birkhoff polytope of doubly stochastic matrices.) The author characterizes the compressed polytopes by their facet defining inequalities, shows that every compressed is affinely isomorphic to a 0/1-polytope and proves a result about pulling triangulations for highly symmetric polytopes. Also the compressed cut polytopes are characterized, and the connection between compressed polytopes and linear optimization is investigated. The last part of the paper refers to applications of these results in statistical disclosure limitation providing new families of marginals where linear programming yields sharp upper bounds on cell entries. These results also refer to integer programming.

MSC:
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
90C10 Integer programming
62H17 Contingency tables
52C07 Lattices and convex bodies in \(n\) dimensions (aspects of discrete geometry)
Software:
polymake
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[2] F. Barahona and A. R. Mahjoub, On the cut polytope, Math. Programming 36 (1986), 157–173. · Zbl 0616.90058 · doi:10.1007/BF02592023
[3] L. Buzzigoli and A. Giusti, An algorithm to calculate the lower and upper bounds of the elements of an array given its marginals, Statistical Data Protection Proceedings, 131–147, Eurostat, Luxembourg, 1999.
[4] S. D. Chowdhury, G. T. Duncan, R. Krishnan, S. F. Roehrig and S. Mukherjee, Disclosure detection in multivariate categorical databases: auditing confidentiality protection through two new matrix operators, Management Science 45 (1999), 1710–1723. · Zbl 1231.91298
[5] M. M. Deza and M. Laurent, Geometry of cuts and metrics, Algorithms Combin. 15, Springer-Verlag, Berlin, 1997. · Zbl 0885.52001
[6] P. Diaconis and B. Sturmfels, Algebraic algorithms for sampling from conditional distributions, Ann. Statist. 26 (1998), 363–397. · Zbl 0952.62088 · doi:10.1214/aos/1030563990
[7] N. Eriksson, S. E. Fienberg, A. Rinaldo and S. Sullivant, Polyhedral conditions for the nonexistence of the MLE for hierarchical log-line models, J. Symbolic Comput. 41 (2006), 222–233. · Zbl 1120.62015 · doi:10.1016/j.jsc.2005.04.003
[8] E. Gawrilow and M. Joswig, Polymake: a framework for analyzing convex polytopes, Polytopes–combinatorics and computation (Oberwolfach, 1997), DMV Sem. 29, Birkäuser, Basel, 2000. · Zbl 0960.68182
[9] C. Haase, Lattice polytopes and unimodular triangulations, Dissertation, TU Berlin, 2000. · Zbl 1066.14508
[10] S. Hoşten and B. Sturmfels, Computing the integer programming gap, To appear in Combinatorica, · Zbl 1136.13016 · doi:10.1007/s00493-007-2057-3
[11] H. Ohsugi and T. Hibi, Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, Proc. Amer. Math. Soc. 129 (2001), 2541–2546. JSTOR: · Zbl 0984.13014 · doi:10.1090/S0002-9939-01-05853-1 · links.jstor.org
[12] P. D. Seymour, Matroids and multicommodity flows, European J. Combin. 2 (1981), 257–290. · Zbl 0479.05023 · doi:10.1016/S0195-6698(81)80033-9
[13] R. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333–342. · Zbl 0812.52012 · doi:10.1016/S0167-5060(08)70717-9
[14] B. Sturmfels, Gröbner bases and convex polytopes, Univ. Lecture Ser. 8, Amer. Math. Soc., Providence, R.I., 1995. · Zbl 0856.13020
[15] G. Ziegler, Lectures on polytopes, Grad. Texts in Math. 152, Springer-Verlag, New York, 1995. · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.