Compressed polytopes and statistical disclosure limitation

Seth Sullivant

Type: Article

Publication Date: 2006-09-01

Citations: 86

DOI: https://doi.org/10.2748/tmj/1163775139

Abstract

We provide a characterization of the compressed lattice polytopes in terms of their facet defining inequalities and prove 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.

Locations

Tohoku Mathematical Journal - View - PDF
arXiv (Cornell University) - PDF

Similar Works

Action	Title	Year	Authors
+	Compressed polytopes and statistical disclosure limitation	2004	Seth Sullivant
+ PDF Chat	Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs	2021	Pravesh K. Kothari Raghu Meka Prasad Raghavendra
+	Convex Discrete Optimization	2007	Shmuel Onn
+	Convex Discrete Optimization	2007	Shmuel Onn
+ PDF Chat	Convex Discrete Optimization	2012
+	Linear programming and combinatorics	1979	Alan J. Hoffman
+	Approximation Limits of Linear Programs (Beyond Hierarchies)	2012	Gábor Braun Samuel Fiorini Sebastian Pokutta David Steurer
+	Approximation Limits of Linear Programs (Beyond Hierarchies)	2012	Gábor Braun Samuel Fiorini Sebastian Pokutta David Steurer
+ PDF Chat	High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts	2020	Monaldo Mastrolilli
+	High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts	2017	Monaldo Mastrolilli
+	On 2-level polytopes arising in combinatorial settings	2017	Manuel Aprile Alfonso Cevallos Yuri Faenza
+	Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy	2005	M. Alekhnovich Sanjeev Arora Iannis Tourlakis
+	Affine reductions for LPs and SDPs	2014	Gábor Braun Sebastian Pokutta Daniel M. Zink
+	Affine reductions for LPs and SDPs	2014	Gábor Braun Sebastian Pokutta Daniel Zink
+ PDF Chat	Tractable Optimization Problems through Hypergraph-Based Structural Restrictions	2009	Georg Gottlob Gianluigi Greco Francesco Scarcello
+ PDF Chat	Facets of a mixed-integer bilinear covering set with bounds on variables	2019	Hamidur Rahman Ashutosh Mahajan
+	Mixed lattice polytope theory with a view towards sparse polynomial systems	2020	Christopher Borger
+ PDF Chat	Approximation Limits of Linear Programs (Beyond Hierarchies)	2015	Gábor Braun Samuel Fiorini Sebastian Pokutta David Steurer
+ PDF Chat	Extended formulations for matroid polytopes through randomized protocols	2022	Manuel Aprile
+	High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts	2017	Monaldo Mastrolilli

Works That Cite This (82)

Action	Title	Year	Authors
+	Lipschitz polytopes of posets and permutation statistics	2018	Raman Sanyal Christian Stump
+ PDF Chat	Bounds on the Number of 2-Level Polytopes, Cones, and Configurations	2021	Samuel Fiorini Marco Macchia Kanstantsin Pashkovich
+	Existence of unimodular triangulations - positive results	2014	Christian Haase Andreas Paffenholz Lindsay C. Piechnik Francisco Santos
+ PDF Chat	Many 2-Level Polytopes from Matroids	2015	Francesco Grande Juanjo Rué
+	Moment Maps, Strict Linear Precision, and Maximum Likelihood Degree One	2018	Patrick Clarke David A. Cox
+ PDF Chat	Theta Bodies for Polynomial Ideals	2010	João Gouveia Pablo A. Parrilo Rekha R. Thomas
+ PDF Chat	Convex Hulls of Algebraic Sets	2011	João Gouveia Rekha R. Thomas
+ PDF Chat	A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs	2010	João Gouveia Monique Laurent Pablo A. Parrilo Rekha R. Thomas
+	Theta Bodies for Polynomial Ideals	2010	Pablo A. Parrilo Rekha R. Thomas João Gouveia
+ PDF Chat	Torsionfreeness for divisor class groups of toric rings of integral polytopes	2024	Koji Matsushita

Works Cited by This (9)

Action	Title	Year	Authors
+	Decompositions of Rational Convex Polytopes	1980	Richard P. Stanley
+	Convex polytopes all of whose reverse lexicographic initial ideals are squarefree	2001	Hidefumi Ohsugi Takayuki Hibi
+ PDF Chat	Algebraic algorithms for sampling from conditional distributions	1998	Persi Diaconis Bernd Sturmfels
+ PDF Chat	Computing the integer programming gap	2007	Serkan Hoşten Bernd Sturmfels
+	On the cut polytope	1986	Francisco Barahona Ali Ridha Mahjoub
+	Gröbner bases and convex polytopes	1995	Bernd Sturmfels
+	Polyhedral conditions for the nonexistence of the MLE for hierarchical log-linear models	2005	Nicholas Eriksson Stephen E. Fienberg Alessandro Rinaldo Seth Sullivant
+	polymake: a Framework for Analyzing Convex Polytopes	2000	Ewgenij Gawrilow Michael Joswig
+ PDF Chat	Gröbner Bases and Convex Polytopes	1995	Bernd Sturmfels