期刊
LINEAR ALGEBRA AND ITS APPLICATIONS
卷 521, 期 -, 页码 217-239出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2016.12.023
关键词
Nonnegative rank; Extension complexity; Regular n-gons; Nonnegative factorization; Boolean rank
资金
- F.R.S-FNRS [F.4501.16]
- ERC [679515]
- Interuniversity Attraction Poles Programme
- Belgian State, Science Policy Office
- Federation Wallonia Brussels [ARC 14/19-060]
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 (2012) [9]. 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 2 [log(2)(n)] by one when 2(k-1) < n <= 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, 9 <= n <= 13 and 21 <= n <= 24) hence allowing for the first time to determine their extension complexity. (C) 2017 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据