MF-AOA asymptotic performance conjecture for the binary paint shop problem

Let $n$ denote the size of a binary paint shop problem (BPSP) instance, let $u(3,\boldsymbol{\gamma},\boldsymbol{\beta})$ denote the performance function for the MF-AOA at the relevant variational parameters, and let AMP denote approximate message-passing algorithms. The normalized paint swap ratio is written as $\mathbb{E}\Delta_C/n$.

MF-AOA asymptotic performance conjecture. In the limit $n\rightarrow\infty$, AMP algorithms such as the MF-AOA achieve a performance of approximately

$$\lim_{n\rightarrow\infty} \mathbb{E}\Delta_C/n = 1-\frac{2\nu(3,\boldsymbol{\gamma},\boldsymbol{\beta})}{\sqrt{3}} \gtrsim 0.269.$$

This conjecture extrapolates the observed QAOA and MF-AOA performance to the large-instance limit. The authors caution that the fitted value may be an overestimate; numerical simulations report an expected normalized paint swap ratio of approximately $0.27993$ for $n=10000$, while a rigorous asymptotic analysis remains to be established.