Tropical lower bounds for extended formulations

• 成果类型: Article
• 署名作者: Shitov, Yaroslav
• 署名单位: HSE University (National Research University Higher School of Economics)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0833-6
• 发表日期: 2015
• 页码: 67-74
• 关键词: nonnegative rank; factorizations; matrices

摘要

The tropical arithmetic operations on , defined as and , arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to develop a method of constructing real polytopes with large extension complexity.