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 |
| _version_ | 1826203238160924672 |
|---|---|
| author | Karp, Richard M. Papadimitriou, Christos H. |
| author_facet | Karp, Richard M. Papadimitriou, Christos H. |
| author_sort | Karp, Richard M. Papadimitriou, Christos H. |
| collection | MIT |
| description | 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-complete combinatorial optimization problems cannot have efficient generators of violated inequalities. |
| first_indexed | 2024-09-23T12:33:48Z |
| id | mit-1721.1/148981 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:33:48Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489812023-03-30T03:44:50Z On Linear Characterizations of Combinatorial Optimization Problems Karp, Richard M. Papadimitriou, Christos H. 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-complete combinatorial optimization problems cannot have efficient generators of violated inequalities. 2023-03-29T14:15:49Z 2023-03-29T14:15:49Z 1980-02 https://hdl.handle.net/1721.1/148981 6681530 MIT-LCS-TM-154 application/pdf |
| spellingShingle | Karp, Richard M. Papadimitriou, Christos H. On Linear Characterizations of Combinatorial Optimization Problems |
| title | On Linear Characterizations of Combinatorial Optimization Problems |
| title_full | On Linear Characterizations of Combinatorial Optimization Problems |
| title_fullStr | On Linear Characterizations of Combinatorial Optimization Problems |
| title_full_unstemmed | On Linear Characterizations of Combinatorial Optimization Problems |
| title_short | On Linear Characterizations of Combinatorial Optimization Problems |
| title_sort | on linear characterizations of combinatorial optimization problems |
| url | https://hdl.handle.net/1721.1/148981 |
| work_keys_str_mv | AT karprichardmpapadimitriouchristosh onlinearcharacterizationsofcombinatorialoptimizationproblems |