目次: :: Library Catalog

保存先:

書誌詳細
第一著者:	Rao, Huiying
フォーマット:	Recurso digital
言語:	英語
出版事項:	Zenodo 2026
主題:	NP-hard loss landscape algorithm selection fitness landscape analysis combinatorial optimisation meta-algorithm landscape classification reconnaissance MCCO
オンライン･アクセス:	https://doi.org/10.5281/zenodo.19697723
タグ:	タグ追加タグなし, このレコードへの初めてのタグを付けませんか!

目次:

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. v2 (2026-04-11): Expanded Related Work with six existing frameworks (Garey & Johnson 1979, FLA/ELA, Algorithm Selection, No Free Lunch, Parameterized Complexity, Learning-Augmented); added cross-framework comparison table; references expanded from 12 to 16. v3 (2026-04-11): Added Scout-Based Algorithm Adjustment and Landscape-Based Parameter Configuration (22 sub-boxes exhaustively enumerated with reconnaissance-based overrides and full parameter lookup tables); Landscape Transformation section (8 transformation methods, 4 difficulty scores, 4-layer stopping conditions with marginal benefit and ROI analysis, precision recovery); Statistical Foundations of Reconnaissance (Type I/II error rates, Power Analysis for scout count, Bonferroni correction, effect size estimation, GP uncertainty propagation); AI-Executable Protocol discussion; three-layer acceleration conclusion (reconnaissance × transformation × AI execution); TSP worked example with three-way comparison (brute force vs blind default vs framework-guided, 0.006s solve time); Scaling test (10/20/50 cities) with "How Close to P?" comparison table (framework at 10⁶ vs brute force at 10⁶⁴); Limitations expanded to 8 items.   v4 (2026-04-12): Three new chapters: <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Landscape Cutting (Decomposition): cutting principles, five cutting tools, six-box cuttability table, transform-first-then-cut ordering, parallel deployment pipeline with global refinement, five cutting considerations.</li> <li class="whitespace-normal break-words pl-2">The Evaluation Matrix: 9 transformations × 4 cuts = 36-cell exhaustive evaluation; empirical validation on 100-city TSP (12 cells in 3.37s); cutting quality check with exhaustibility guarantee.</li> <li class="whitespace-normal break-words pl-2">Algorithm Adequacy Scoring: scale × difficulty → four-tier minimum tool level.</li> </ul> Cross-box empirical validation (six boxes, all new): <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Box 1b TSP: TSPLIB standard benchmarks (eil51/berlin52/kroA100), equal-time-budget fair comparison, framework wins by 4–8% gap reduction.</li> <li class="whitespace-normal break-words pl-2">Box 1a MKP: Multidimensional knapsack (50–500 items, 3–10 constraints), framework wins by 1.4–6.9%, Chu & Beasley (1998) reference added.</li> <li class="whitespace-normal break-words pl-2">Box 2a Graph Coloring: 50–200 nodes, density 0.1–0.5, framework saves 14–30% colors via DSatur + Tabu Search.</li> <li class="whitespace-normal break-words pl-2">Box 3a 3-SAT: tested across phase transition (α = 2.0–5.0), framework selects CDCL for hard instances, solves instances that blind WalkSAT cannot, 15.1× speedup at α = 4.2.</li> <li class="whitespace-normal break-words pl-2">Box 4b VRP: 20–100 customers, framework serves +44 additional customers (coverage 56% → 100%), natural application of cutting mechanism.</li> <li class="whitespace-normal break-words pl-2">Box 5a Scheduling: 20–200 jobs, framework wins by 7–27%, 200-job instance within 0.1% of lower bound.</li> </ul> How Close to P cross-box comparison table: five of eight test cases at or near P, three within 1–2 orders of magnitude, zero large gaps. Improvement acceleration data: 9% at 20 cities → 66% at 50 cities → 80% at 100 cities. Conclusion upgraded: three-layer → four-layer acceleration (reconnaissance × transformation × cutting × AI execution); TSPLIB scaling evidence added. References: 16 → 18 (added Reinelt 1991 TSPLIB, Chu & Beasley 1998 MKP).   v5 (2026-04-13): Unified error architecture across three layers: <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">New Remark in Section 8.3 (Difficulty Scoring): formally establishes that transformation and cutting are deterministic functions of reconnaissance scores, introducing no independent statistical error. All inference risk is concentrated in the reconnaissance layer. Reconnaissance is inference; transformation and cutting are execution.</li> </ul> Score Significance Testing (new Section 10.5): <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">When exhaustive evaluation ranks two cells with similar scores, sampling noise may reverse the ranking. New protocol: paired tt t-test (or Wilcoxon) on top two cells using existing reconnaissance data; significant → deploy winner; not significant → deploy simpler configuration (fewer transformations, fewer cuts). Cost: zero (arithmetic on already-computed data). Only top-two comparison needed (a fortioria\ fortiori a fortiori guarantee for all lower ranks).</li> </ul> Three-layer statistical discipline Remark: <ul class="[li_&]:mb-0 [li_&]:mt-1 [li_&]:gap-1 [&:not(:last-child)_ul]:pb-1 [&:not(:last-child)_ol]:pb-1 list-disc flex flex-col gap-1 pl-8 mb-3"> <li class="whitespace-normal break-words pl-2">Reconnaissance layer controls score accuracy (Type I/II, power analysis, Bonferroni, GP uncertainty).</li> <li class="whitespace-normal break-words pl-2">Exhaustion layer eliminates selection error (all 36 cells evaluated).</li> <li class="whitespace-normal break-words pl-2">Decision layer controls ranking error (score significance test when differences are small).</li> <li class="whitespace-normal break-words pl-2">Defence-first philosophy formally shown to pervade all three layers, not just reconnaissance.</li> </ul> References de-duplicated: removed duplicate entries for Rice (1976) and Wolpert & Macready (1997). Reference count: 18 → 16 (net −2 duplicates removed). Page count: 48 → 49 (+1 page of new statistical framework content, on the original v4 .tex source without content loss).   v6 update: Comprehensive strengthening of the framework along five dimensions. (1) Literature support — every best-fit solver recommendation in every sub-box now has explicit citations (Martello & Toth 1990 for Knapsack, Applegate et al. 2006 for TSP, Nemhauser & Trotter 1975 for Vertex Cover, Chvátal 1979 for Set Cover, Dinur & Steurer 2014 for Dominating Set hardness, and 20+ others). (2) Sub-box boundary refinement — Set Cover removed from Box 1a; Box 2b split into 2b-i (Vertex Cover and Set Cover, admitting constant-factor or logarithmic approximations via LP rounding) and 2b-ii (Dominating Set, admitting no constant-factor approximation unless P=NP); Classification Principle amended to state that sub-box boundaries are determined by landscape structure and approximation hardness rather than superficial semantic similarity. (3) Universality claim tightened — replaced "covers 95% of known NP problems" with "spans all major structural types of NP-hard problems catalogued in Garey & Johnson (1979)"; added new subsection classifying eight modern NP-hard problems (Neural Architecture Search, Hyperparameter Optimisation, Graph Neural Network subgraph matching, Federated Learning client selection, Quantum Circuit Compilation, Blockchain Shard Assignment, Data-centre VM Placement, Model Merging) to demonstrate that the taxonomy extends naturally to problems post-dating the 1979 catalogue. (4) Landscape-Method Compatibility Proposition — introduced as theoretical justification: optimisation methods are effective only when their update operators align with the landscape's structural properties; (problem, method) space admits a natural compatibility partition; accompanied by three canonical mismatch examples (gradient descent on 3-SAT at phase transition, CDCL on continuous optimisation, generic GA on Dominating Set without decomposition) demonstrating that structural incompatibility cannot be remedied by parameter tuning. (5) Three universal quantitative indicators — Ruggedness R (neighbour objective autocorrelation), Constraint Propagation Density D_c (domain reduction ratio after variable fixing), and Gradient Smoothness S_g (Lipschitz constant of relaxation gradient) — with expected ranges tabulated per Box, converting classification from expert judgement into reproducible measurement. Overall effect: framework upgraded from descriptive taxonomy to formally grounded classification system with decidable indicators, theoretical justification, and empirical validation across classical and modern problems.   Version 7 consolidates the framework's formal and statistical foundations along  six dimensions: (i) The Landscape-Method Compatibility Proposition is accompanied by a working  definition of "structural morphism" (neighbourhood preservation and basin  preservation) and an explicit Status remark acknowledging its standing as a  structural principle with empirical support rather than a formally proven theorem. (ii) The Adequacy Score is redefined as an explicit piecewise step function of  problem scale and difficulty rather than an unspecified f(N × D). (iii) Surrogate uncertainty propagation is formalised via inverse-variance  weighting, giving an explicit aggregation formula and standard-error expression  for Gaussian-Process-backed difficulty scores. (iv) The multiple-testing correction section explicitly addresses score  correlation, contrasting Bonferroni with Holm–Bonferroni and Benjamini–Hochberg  alternatives for positive dependence. (v) The inapproximability citation for Dominating Set is corrected to the  Feige (1998) Set-Cover reduction as primary source, with Dinur–Steurer (2014)  retained as tightness reinforcement. (vi) The two separate speedup figures reported for Box 6—MCCO's 24,000×  algorithmic speedup and the reconnaissance-guided 3.56× deployment speedup—are  now explicitly disambiguated to prevent baseline confusion. Version 7 also adds an honest limitation concerning the operational definition  of the ruggedness indicator R: preliminary calibration experiments suggest that  naive lag-1 autocorrelation has limited discriminating power across Box types,  and candidate refinements are listed for future work. Keywords: NP-hard, loss landscape, landscape classification, metaheuristics,  algorithm selection, reconnaissance, problem taxonomy, MCCO

類似資料