Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909650304106496 |
|---|---|
| author | Saidi, Olivier |
| author_facet | Saidi, Olivier |
| contents | NP hard optimization problems like the Traveling Salesman Problem (TSP) defy efficient solutions in the worst case, yet real-world instances often exhibit exploitable patterns. We propose a novel patternaware complexity framework that quantifies and leverages structural regularities e.g., clustering, symmetry to reduce effective computational complexity across domains, including financial forecasting and LLM optimization. With rigorous definitions, theorems, and a meta learning driven solver pipeline, we introduce metrics like Pattern Utilization Efficiency (PUE) and achieve up to 79 percent solution quality gains in TSP benchmarks (22 to 2392 cities). Distinct from theoretical NP hardness, our approach offers a unified, practical lens for pattern-driven efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13810 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study Saidi, Olivier Artificial Intelligence NP hard optimization problems like the Traveling Salesman Problem (TSP) defy efficient solutions in the worst case, yet real-world instances often exhibit exploitable patterns. We propose a novel patternaware complexity framework that quantifies and leverages structural regularities e.g., clustering, symmetry to reduce effective computational complexity across domains, including financial forecasting and LLM optimization. With rigorous definitions, theorems, and a meta learning driven solver pipeline, we introduce metrics like Pattern Utilization Efficiency (PUE) and achieve up to 79 percent solution quality gains in TSP benchmarks (22 to 2392 cities). Distinct from theoretical NP hardness, our approach offers a unified, practical lens for pattern-driven efficiency. |
| title | Bridging Pattern-Aware Complexity with NP-Hard Optimization: A Unifying Framework and Empirical Study |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2506.13810 |