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
Computer Science · Business, Management and Accounting · Engineering · #Computational Geometry and Mesh Generation #Consumer Market Behavior and Pricing #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1605.03243

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