On Linear Characterizations of Combinatorial Optimization Problems
We show that there can be no computationally tractable description by linear inequalities of the polyhedron associated with any NP-complete combinatorial optimization problem unless NP=co-NP -- a very unlikely event. We also use the recent result by Khacian to present even stronger evidence that NP-...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148981 |