On modeling hard combinatorial optimization problems as linear programs: Refutations of the "unconditional impossibility" claims

February 10, 2019 ยท The Ethereal ยท ๐Ÿ› International Journal of Operations Research

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Moustapha Diaby, Mark H. Karwan, Lei Sun arXiv ID 1902.03549 Category cs.CC: Computational Complexity Cross-listed cs.DS, math.OC Citations 0 Venue International Journal of Operations Research Last Checked 3 months ago
Abstract
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 exists no abstraction of an NP-Complete combinatorial optimization problem in which the defining combinatorial configurations (such as "tours" in the case of the traveling salesman problem (TSP) for example) can be modeled by a polynomial-sized system of linear constraints. The purpose of this paper is to provide general as well as specific refutations for these recent claims.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity