Large Shadows from Sparse Inequalities
METADATA ONLY
Loading...
Author / Producer
Date
2013-08-12
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The d-dimensional Goldfarb cube is a polytope with the property that all its 2^d vertices appear on some \emph{shadow} of it (projection onto a 2-dimensional plane). The Goldfarb cube is the solution set of a system of 2d linear inequalities with at most 3 variables per inequality. We show in this paper that the d -dimensional Klee-Minty cube --- constructed from inequalities with at most 2 variables per inequality --- also has a shadow with 2^d vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
Cornell University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
Submitted on 12 August 2013.