| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
On the Linear Extension Complexity of Regular n-gons | Arnaud Vandaele
; Nicolas Gillis
; François Glineur
; | Date: |
29 May 2015 | Abstract: | In this paper, we propose a new upper bound on the linear extension
complexity of regular $n$-gons. It is 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$. We provide explicit nonnegative factorizations for the slack matrix of any
regular $n$-gons of size $2 lceil log_2(n)
ceil - 1$ if $2^{k-1} < n leq
2^{k-1}+2^{k-2}$ for some integer $k$, and of size $2 lceil log_2(n)
ceil$
if $2^{k-1}+2^{k-2} < n leq 2^{k}$. For $2^{k-1}+2^{k-2} < n leq 2^{k}$, our
bound coincides with the best known upper bound of $2 leftlceil log_2(n)
ight
ceil$ by Fiorini, Rothvoss and Tiwary [Extended Formulations for
Polygons, Discrete Comput. Geom. 48(3), pp. 658-668, 2012]. We conjecture that
our 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, $9 leq n leq 14$
and $21 leq n leq 24$) hence allowing for the first time to determine their
extension complexity. | Source: | arXiv, 1505.8031 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |