A geometric lower bound on the extension complexity of polytopes based on the f-vector

Julien Dewez, Nicolas Gillis and François Glineur
Additional contact information
Julien Dewez: Université catholique de Louvain, LIDAM/CORE, Belgium
Nicolas Gillis: Université de Mons

No 3172, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: A linear extension of a polytope is any polytope which can be mapped onto via an affine transformation. The extension complexity of a polytope is the minimum number of facets of any linear extension of this polytope. In general, computing the extension complexity of a given polytope is difficult. The extension complexity is also equal to the nonnegative rank of any slack matrix of the polytope. In this paper, we introduce a new geometric lower bound on the extension complexity of a polytope, i.e., which relies only on the knowledge of some of its geometric characteristics. It is based on the monotone behaviour of the -vector of polytopes under affine maps. We present numerical results showing that this bound can improve upon existing geometric lower bounds, and provide a generalization of this lower bound for the nonnegative rank of any matrix.

Keywords: Applied Mathematics; Discrete Mathematics and Combinatorics; Convex polytopes; Combinatorial optimization; Linear extension; Extended formulation; Extension complexity; Lower bound; Slack matrices; Nonnegative matrix factorization; Nonnegative rank; Restricted nonnegative rank (search for similar items in EconPapers)
Pages: 17
Date: 2021-01-01
Note: In: Discrete Applied Mathematics, vol. 303, p. 22-38 (2021)
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3172

DOI: 10.1016/j.dam.2020.09.028

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().