2013/08/12 by Bernd Gärtner, Gärtner, Bernd, Christian Helbling +5
Computer Science · Engineering · Mathematics · #05A99 #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1308.2495
openalex publication_date 2013/08/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The d-dimensional Goldfarb cube is a polytope with the property that all its 2d vertices appear on some 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 2d vertices. In contrast, with one variable per inequality, the size of the shadow is bounded by 2d.