Compressed polytopes and statistical disclosure limitation

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

Authors: Seth Sullivant 

Publication date: 13 April 2007

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

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.

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

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
• Enumeration of 2-level polytopes

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)

Cites Work

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

Cited In (42)

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

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)