95.91% of best-known solutions on Gset · G81 (20,000 nodes) · under 5 minutes · CPU only · <80 MB RAM
An adaptive local-search selector for the MAX-CUT problem. The Meta-Engine chooses perturbation intensity (1%, 3%, or 10% vertex flips) based on current solution quality, reaching near-best-known cuts on large sparse graphs using only commodity CPU hardware.
Using the Meta-Engine, we observe that the optimal perturbation operation changes sharply near a threshold of solution quality: T_empirical = 0.950 ± 0.001 (255 measurements, 6 topologies, 5 sizes) This threshold is stable across graph topology and size. We note that it falls numerically close to the Håstad inapproximability bound 16/17 ≈ 0.9412 (Δ = 0.009), but our size-convergence test shows T_emp does not converge to 16/17 as n grows (slope ≈ -6e-8) — they appear to be distinct phenomena, not a single underlying constant. We make no claim of a proven connection; this is an empirical observation inviting theoretical investigation.
| Graph | Vertices | Cut | % of Best-Known | Time |
|---|---|---|---|---|
| G62 | 7,000 | 4,656 | 95.61% | 2 min |
| G66 | 9,000 | 6,076 | 95.47% | 2 min |
| G67 | 10,000 | 6,664 | 96.02% | 2 min |
| G70* | 10,000 | 9,347 | 97.97% | 2 min |
| G72 | 10,000 | 6,690 | 95.46% | 2 min |
| G77 | 14,000 | 9,476 | 95.33% | 3 min |
| G81 | 20,000 | 13,428 | 95.50% | 5 min |
| Mean | — | — | 95.91% | <5 min |
All results: single CPU core · <80 MB RAM · no GPU · fixed thresholds T₁ = 0.85, T₂ = 0.92, no graph-specific tuning.
*G70 is a near-tree instance (|E| ≈ |V|−1) and behaves differently; see preprint.
| Algorithm | % of Best-Known | Time | Hardware |
|---|---|---|---|
| Cosm (Zick, 2025) | 100% | — | specialized CMOS |
| BLS (Benlic & Hao, 2013) | 99.8% | up to 5.6 h | CPU |
| GravOpt Meta-Engine | 95.5% | 5 min | standard CPU |
| Fixed Perturb-10% | 91.3% | 2 min | CPU |
GravOpt does not beat state-of-the-art solvers on solution quality. Its value is reaching ~96% of best-known quickly on commodity hardware with no tuning — a practical trade-off, not a record.
quality < 85% → perturb 10% + local search (coarse)
quality 85–92% → perturb 3% + local search (medium)
quality > 92% → perturb 1% + local search (fine) This gives +4.39% over a fixed Perturb-10% strategy under equal time budget.
pip install numpy numba
python meta_engine.py G81.txt run 300
python threshold_discovery.pymeta_engine.py Adaptive Meta-Engine (main solver)
threshold_discovery.py Perturbation-regime threshold measurement
vlsi_bipartition.py Experimental: VLSI partitioning trial
All benchmark data, seeds, and code are in the Zenodo record:
- Zenodo: doi.org/YOUR_CANONICAL_DOI
- 255 measurements across 9 conditions
- Seeds: [1, 2, 3, 4, 5]; sizes: [500, 1000, 2000, 5000, 10000]
Preprint (not peer-reviewed): Research Square, DOI 10.21203/rs.3.rs-9763617/v1
MIT License — free for research and commercial use with attribution.
@misc{kretski2026maxcut,
author = {Kretski, Dimitar Vasilev},
title = {An Empirical Perturbation-Regime Transition in MAX-CUT
Local Search: Evidence from a Multi-Topology Benchmark},
year = {2026},
doi = {YOUR_CANONICAL_DOI},
note = {Preprint, Research Square}
}Independent research · Varna, Bulgaria · kretski1@gmail.com