From a floating-point candidate to a checkable guarantee of positivity, exact feasibility, and bounded objective error—directly on the original sparse problem.
Preprint · Not peer-reviewed · arXiv submission pending category endorsement; no arXiv identifier assigned.
The numerical solver proposes a potential. A separate replay is the sole authority for acceptance.
A finite dual candidate from any numerical solver.
Untrusted candidateReciprocal KKT allocation with a canonical spanning-tree correction.
Implicit exact-real flowSigned, outward-rounded arithmetic checks the same recovered allocation.
Accept or rejectThe linear-work claim applies to verification with precompiled, fixed-topology schedules—not to the entire solve. Exact feasibility belongs to the implicit real allocation; the returned binary64 vector is approximate. A separate rational format supports explicit exact-feasible decisions.
Matched problem fingerprints, saved accuracy targets, and independent integer/rational checks.
18 shared problems · 300 or 1,000 edges
| Tested implementation | At shared ε |
|---|---|
| CertQuota public cold pipeline | 18 / 18 |
| CertQuota on the same SeDuMi dual | 18 / 18 |
| Experimental VSDP interval port | 15 / 18 |
All 18 port brackets are finite and independently witnessed; three miss the common tolerance. The dense Octave-interval compatibility port is not stock VSDP/INTLAB. These observations are not a universal solver ranking.
Recheck the synthetic problems with Python's standard library. No CertQuota, NumPy, Arb, or VSDP imports are needed.
Download the witness archive ↗The local audit checks 114 objects. The 24 MovieLens-derived objects are not redistributed under the dataset's permission requirement.
All 36 valid starts eventually pass only with explicit extra retry stages. All 18 invalid-domain controls are rejected.
Rebuild-on-rejection and always-rebuild both pass 216/216 cells. These are correlated measurements from nine graphs.
Historical MovieLens inputs with nonzero cost and quota proxies. One dataset, not a production deployment or a recommendation-quality claim.
Source: the A45 revision and independent-witness appendix in the paper. Numerical evidence is not a substitute for independent human proof review.
Small, inspectable components with a documented finite-precision contract.
Mathematical development, experiments, limitations, and declarations.
CertQuota 0.2.0 · BSD-3-Clause software · Python 3.10+
Portable TeX source, synthetic witnesses, and SHA-256 manifest.
35 core tests and three independently checked 1,024-edge examples on each platform. Portability check, not a full timing rerun.
Only an accepted strict certificate authorizes an allocation. A solver status alone does not.
Read the reproduction guide ↗git clone https://github.com/long-0228/certquota.git
cd certquota
python -m pip install .
python examples/solve_and_replay.pyThis is a curated public snapshot, not the complete historical local experiment environment. Raw MovieLens data, dataset-derived proof arrays, proprietary interval software, and third-party solver binaries are excluded.
The citation will be updated when an arXiv identifier or journal record is available.
Download BibTeX ↓@misc{li2026certquota,
author = {Li, Long},
title = {A Solver-Independent, Fixed-Topology
Linear-Work Endpoint Certificate for
Sparse Reciprocal Transportation},
year = {2026},
howpublished = {Preprint},
url = {https://long-0228.github.io/certquota/}
}