On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913468813148160 |
|---|---|
| author | Diaby, Moustapha Karwan, Mark Sun, Lei |
| author_facet | Diaby, Moustapha Karwan, Mark Sun, Lei |
| contents | 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 Combinatorial Optimization. Journal of the ACM 62:2"), we focus in this paper on the question of whether it is possible to model an NP-Complete problem as a polynomial-sized linear program. For the sake of simplicity of exposition, the discussions are focused on the TSP. We show that a finding that there exists no polynomial-sized extended formulation of "the TSP polytope" does not (necessarily) imply that it is "impossible" for a polynomial-sized linear program to solve the TSP optimization problem. We show that under appropriate conditions the TSP optimization problem can be solved without recourse to the traditional city-to-city ("travel leg") variables, thereby side-stepping/"escaping from" "the TSP polytope" and hence, the barriers. Some illustrative examples are discussed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_07716 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers" Diaby, Moustapha Karwan, Mark Sun, Lei Computational Complexity Data Structures and Algorithms Optimization and Control 90-08, 90-10 F.2.2; G.2 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 Combinatorial Optimization. Journal of the ACM 62:2"), we focus in this paper on the question of whether it is possible to model an NP-Complete problem as a polynomial-sized linear program. For the sake of simplicity of exposition, the discussions are focused on the TSP. We show that a finding that there exists no polynomial-sized extended formulation of "the TSP polytope" does not (necessarily) imply that it is "impossible" for a polynomial-sized linear program to solve the TSP optimization problem. We show that under appropriate conditions the TSP optimization problem can be solved without recourse to the traditional city-to-city ("travel leg") variables, thereby side-stepping/"escaping from" "the TSP polytope" and hence, the barriers. Some illustrative examples are discussed. |
| title | On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers" |
| topic | Computational Complexity Data Structures and Algorithms Optimization and Control 90-08, 90-10 F.2.2; G.2 |
| url | https://arxiv.org/abs/2304.07716 |