๐ฎ
๐ฎ
The Ethereal
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
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Computational Complexity
๐ฎ
๐ฎ
The Ethereal
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
๐ฎ
๐ฎ
The Ethereal
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
๐ฎ
๐ฎ
The Ethereal
The Hardness of Approximation of Euclidean k-means
๐ฎ
๐ฎ
The Ethereal
Slightly Superexponential Parameterized Problems
๐ฎ
๐ฎ
The Ethereal