Native Rectangular Linear Assignment with Implicit Rejection: A Jonker-Volgenant Solver without Square Expansion

Overview & Synopsis

Tracking and matching applications often solve rectangular assignment with a uniform penalty for leaving elements unmatched. Widely used tracking interfaces embed the $N \times M$ costs in an (N+M)-square matrix: for 256 rows and 4096 columns, 144.5 MiB of costs for an 8 MiB problem. We describe a Jonker-Volgenant implementation that keeps the real matrix and represents rejection inside its shortest-path search by one terminal distance and one predecessor row. Building on established rectangular and optional-assignment formulations, we derive the one-sided objective and its primal-dual certificate. Rust (JVRUST), hybrid Rust/C++ (JVHYBRID), and C++ (JVCPP) implementations with native batching agree with exhaustive enumeration and are compared with expanded solvers and an exact capped-cost SciPy formulation. Two environments, Python 3.14.9 and 3.11.17 on one Intel/Windows host, each provide 8,946 timing samples across 204 cases, including 5000-square matrices, extreme aspect ratios, structured costs, and rejection sweeps. JVRUST beats capped SciPy in the same nine of ten formulation cases; JVRUST and JVCPP each preserve their ordering against the relevant SciPy baseline in all 201 non-batch cases. Congestion remains a counterexample: capped SciPy is about 9.4 and 9.1 times faster at $1024 \times 1280$. For small problems, JVRUST's four-worker batching improves on its sequential Python loop by 5.1 and 4.7 times. Repeated memory measurements confirm the cost of square expansion and an orientation-dependent native footprint. These results characterize particular implementations and software environments; they do not isolate a Python-version or programming-language effect.