Compressed polytopes and statistical disclosure limitation

DOI10.2748/TMJ/1163775139zbMATH Open1121.52028OpenAlexW1989517190MaRDI QIDQ875709FDOQ875709

Authors Seth Sullivant 

Publication date 13 April 2007

Published in Tôhoku Mathematical Journal. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingalgebraic statisticsBirkhoff polytopeinteger programmingaffine symmetrydisclosure limitation0/1-polytopecompressed polytope

Mathematics Subject Classification ID

Contingency tables (62H17) Integer programming (90C10) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: We provide a characterization of the compressed lattice polytopes in terms of their facet defining inequalities and we show that every compressed lattice polytope is affinely isomorphic to a 0/1-polytope. As an application, we characterize those graphs whose cut polytopes are compressed and discuss consequences for studying linear programming relaxations in statistical disclosure limitation.

Recommendations

• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Extreme points of the local differential privacy polytope
• Integer Programming and Combinatorial Optimization
• The \(h\)-vector of a Gorenstein toric ring of a compressed polytope

Cites work

• scientific article; zbMATH DE number 2186838 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Algebraic algorithms for sampling from conditional distributions
• Computing the integer programming gap
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Decompositions of Rational Convex Polytopes
• Disclosure detection in multivariate categorical databases: auditing confidentiality protection through two new matrix operators
• Geometry of cuts and metrics
• Lectures on Polytopes
• Matroids and multicommodity flows
• On the cut polytope
• Polyhedral conditions for the nonexistence of the MLE for hierarchical log-linear models
• polymake: a framework for analyzing convex polytopes

Cited in

(39)

• Normality of cut polytopes of graphs is a minor closed property
• Convex polytopes all of whose reverse lexicographic initial ideals are squarefree
• Torsionfreeness for divisor class groups of toric rings of integral polytopes
• Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes
• Bounds on the number of 2-level polytopes, cones, and configurations
• A generalization of the integer linear infeasibility problem
• Toric geometry of cuts and splits
• Two double poset polytopes
• Unconditional reflexive polytopes
• The reflexive dimension of (0, 1)-polytopes
• Many 2-level polytopes from matroids
• Quadratic Gröbner bases for smooth \(3\times 3\) transportation polytopes
• \(S\)-hypersimplices, pulling triangulations, and monotone paths
• Low dimensional flow polytopes and their toric ideals
• Theta rank, levelness, and matroid minors
• Markov degree of the Birkhoff model
• Seminormality, canonical modules, and regularity of cut polytopes
• Gelfand-Tsetlin polytopes and the integer decomposition property
• Non-Normal Very Ample Polytopes – Constructions and Examples
• Reflexive polytopes arising from perfect graphs
• The Martin Gardner Polytopes
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Convex hulls of algebraic sets
• Existence of unimodular triangulations -- positive results
• Lipschitz polytopes of posets and permutation statistics
• Integer Programming and Combinatorial Optimization
• Moment maps, strict linear precision, and maximum likelihood degree one
• Gorenstein cut polytopes
• Grid graphs, Gorenstein polytopes, and domino stackings
• Delannoy orthants of Legendre polytopes
• Reflexive polytopes arising from edge polytopes
• Perfectly contractile graphs and quadratic toric rings
• Normal binary hierarchical models
• Enriched chain polytopes
• Indispensable monomials of toric ideals and Markov bases
• Toric rings of \((0, 1)\)-polytopes with small rank
• Toric rings of perfectly matchable subgraph polytopes
• Generalized cut polytopes for binary hierarchical models
• Incompatible double posets and double order polytopes

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Compressed polytopes and statistical disclosure limitation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q875709)