5 papers
On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
Moustapha Diaby, Mark Karwan, Lei Sun
In view of the extended formulations (EFs) developments (e.g. "Fiorini, S., S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf [2015]. Exponential Lower Bounds for Polytopes in Com…
On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims
Moustapha Diaby, Mark H. Karwan, Lei Sun
There has been a series of developments in the recent literature (by essentially a same "circle" of authors) with the absolute/unconditioned (implicit or explicit) claim that there…
On "Exponential Lower Bounds for Polytopes in Combinatorial Optimization" by Fiorini et al. (2015): A Refutation For Models With Disjoint Sets of Descriptive Variables
Moustapha Diaby, Mark H. Karwan, Lei Sun
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…
Limits to the scope of applicability of extended formulations for LP models of combinatorial optimization problems: A summary
Moustapha Diaby, M. H. Karwan
We show that new definitions of the notion of "projection" on which some of the recent "extended formulations" works (such as Kaibel (2011); Fiorini et al. (2011; 2012); Kaibel and…
On Limits to the Scope of the Extended Formulations "Barriers"
Moustapha Diaby, M. H. Karwan
In this paper, we introduce the notion of augmentation for polytopes and use it to show the error in two presumptions that have been key in arriving at over-reaching/over-scoped cl…