On the linear extension complexity of regular n-gons

DOI10.1016/J.LAA.2016.12.023MaRDI QIDQ513256zbMATH OpenOpenAlexFDO

Authors Arnaud Vandaele, Nicolas Gillis, François Glineur

Publication date 3 March 2017

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.08031

zbMATH Keywords

extension complexitynonnegative ranknonnegative factorizationBoolean rankregular \(n\)-gons

Mathematics Subject Classification ID

Factorization of matrices (15A23) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Combinatorial complexity of geometric structures (52C45)

Abstract: In this paper, we propose new lower and upper bounds on the linear extension complexity of regular $n$-gons. Our bounds are based on the equivalence between the computation of (i) an extended formulation of size $r$ of a polytope $P$, and (ii) a rank-$r$ nonnegative factorization of a slack matrix of the polytope $P$. The lower bound is based on an improved bound for the rectangle covering number (also known as the boolean rank) of the slack matrix of the $n$-gons. The upper bound is a slight improvement of the result of Fiorini, Rothvoss and Tiwary [Extended Formulations for Polygons, Discrete Comput. Geom. 48(3), pp. 658-668, 2012]. The difference with their result is twofold: (i) our proof uses a purely algebraic argument while Fiorini et al. used a geometric argument, and (ii) we improve the base case allowing us to reduce their upper bound $2leftlceillo{g}_2(n)ightceil$ by one when $2^{k-1}<nleq{2}^{k-1}+2^{k-2}$ for some integer $k$. We conjecture that this new upper bound is tight, which is suggested by numerical experiments for small $n$. Moreover, this improved upper bound allows us to close the gap with the best known lower bound for certain regular $n$-gons (namely, $9leqnleq13$ and $21leqnleq24$) hence allowing for the first time to determine their extension complexity.

Recommendations

• Extended formulations for polygons
• On ranks of regular polygons
• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• Combinatorial bounds on nonnegative rank and extended formulations

Cites work

• scientific article; zbMATH DE number 4031722 (Why is no real title available?)
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)
• A short proof of Sperner's lemma
• An upper bound for nonnegative rank
• Combinatorial bounds on nonnegative rank and extended formulations
• Constructing extended formulations from reflection relations
• Constructing extended formulations from reflection relations
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for polygons
• Heuristics for exact nonnegative matrix factorization
• Lectures on Polytopes
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations
• Lower bounds on nonnegative rank via nonnegative nuclear norms
• On Polyhedral Approximations of the Second-Order Cone
• On the geometric interpretation of the nonnegative rank
• Real rank versus nonnegative rank
• Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
• Smallest compact formulation for the permutahedron
• The maximum numbers of faces of a convex polytope
• Which nonnegative matrices are slack matrices?

Cited in

(8)

• A geometric lower bound on the extension complexity of polytopes based on the f-vector
• Extended formulations for convex heptagons
• Lifting for simplicity: concise descriptions of convex sets
• Algorithms for positive semidefinite factorization
• Extended formulations for polygons
• Heuristics for exact nonnegative matrix factorization
• Maximum semidefinite and linear extension complexity of families of polytopes
• On ranks of regular polygons

This page was built for publication: On the linear extension complexity of regular \(n\)-gons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513256)