28 citations · 29 across the 13 of their papers we have counts for
8 papers · 1 filter
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…
A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"
Moustapha Diaby
Using an approach that seems to be patterned after that of Yannakakis, Hofman argues that an NP-complete problem cannot be formulated as a polynomial bounded-sized linear programmi…
On "P = NP: Linear Programming Formulation of the Traveling Salesman Problem": A reply to Hofman's Claim of a "Counter-Example"
Moustapha Diaby
We show that Hofman's claim of a "counter-example" to Diaby's LP formulation of the TSP is invalid.