On "Exponential Lower Bounds for Polytopes in Combinatorial Optimization" by Fiorini et al. (2015): A Refutation For Models With Disjoint Sets of Descriptive Variables

2016/05/10 by Moustapha Diaby, Diaby, Moustapha, Mark H. Karwan +3
Business, Management and Accounting · Computer Science · Engineering · Mathematics · #Combinatorics #Computational Geometry and Mesh Generation #Consumer Market Behavior and Pricing #Disjoint sets #Exponential function #Mathematical analysis #Mathematics #Polytope #Vehicle Routing Optimization Methods #cs.CC #cs.DM #cs.DS #math.OC

paper · pdf · doi:10.48550/arxiv.1605.03243

published in arXiv (Cornell University) (Cornell University) · 7 pages; Minor typos fixed; Presentation of counter-example simplified

openalex publication_date 2016/05/10 · arxiv created 2016/06/21 · openalex created_date 2016/06/24 · arxiv updated 2016/10/21 · openalex updated_date 2026/07/28

Abstract

We provide a numerical refutation of the developments of Fiorini et al. (2015)* for models with disjoint sets of descriptive variables. We also provide an insight into the meaning of the existence of a one-to-one linear map between solutions of such models. *: Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf (2015). Exponential Lower Bounds for Polytopes in Combinatorial Optimization. Journal of the ACM 62:2, Article No. 17.

Related

• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
• Combinatorial Bounds on Nonnegative Rank and Extended Formulations
• Extended Formulations in Combinatorial Optimization
• On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims