Removing degeneracies in LP-type problems may need to increase dimension

Abstract

We construct an example of LP-type problem of dimension 4, for which any nondegenerate refinement has dimension at least 6. We show how this relates to the problem of covering of a certain poset by Boolean algebras.

Keywords

• Removing
• degeneracies
• LP-type
• problems
• increase
• dimension