A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection
Fuente:
Zenodo
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Recurso digital |
| Langue: | anglais |
| Publié: |
Zenodo
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866901877383233536 |
|---|---|
| author | Rao, Huiying |
| author_facet | Rao, Huiying |
| contents | <p>We propose a unified classification framework for NP-hard problems based on loss landscape topology. The framework classifies 95% of known NP problems into seven boxes (combinatorial optimisation, graph theory, logical satisfaction, path/network, permutation/assignment, sequential decision, miscellaneous), further divided into 24 sub-boxes each with formal objective functions. A three-tier reconnaissance system (aerial survey, scout sampling, mass sampling) analyses landscape topology before algorithm selection. A five-cut decision tree maps landscape properties to optimal solvers and parameter configurations. All 22 sub-boxes are exhaustively enumerated with default algorithms, scout-based adjustments, and landscape-based parameter settings. Box 6 (sequential decision) is fully validated using MCCO as proof of concept, demonstrating 3.56× speedup via landscape-guided deployment. The framework draws an analogy to database normalisation: just as complex data can be decomposed through finite normal forms, complex NP problems can be classified through finite landscape cuts. ORCID: 0009-0002-9497-1336.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19512006 |
| institution | Zenodo |
| language | eng |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection Rao, Huiying NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO <p>We propose a unified classification framework for NP-hard problems based on loss landscape topology. The framework classifies 95% of known NP problems into seven boxes (combinatorial optimisation, graph theory, logical satisfaction, path/network, permutation/assignment, sequential decision, miscellaneous), further divided into 24 sub-boxes each with formal objective functions. A three-tier reconnaissance system (aerial survey, scout sampling, mass sampling) analyses landscape topology before algorithm selection. A five-cut decision tree maps landscape properties to optimal solvers and parameter configurations. All 22 sub-boxes are exhaustively enumerated with default algorithms, scout-based adjustments, and landscape-based parameter settings. Box 6 (sequential decision) is fully validated using MCCO as proof of concept, demonstrating 3.56× speedup via landscape-guided deployment. The framework draws an analogy to database normalisation: just as complex data can be decomposed through finite normal forms, complex NP problems can be classified through finite landscape cuts. ORCID: 0009-0002-9497-1336.</p> |
| title | A Landscape Classification Framework for NP-Hard Problems: From Reconnaissance to Algorithm Selection |
| topic | NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO |
| url | https://doi.org/10.5281/zenodo.19512006 |