MF-AOA asymptotic performance conjecture for the binary paint shop problem
Statement
Let denote the size of a binary paint shop problem (BPSP) instance, let 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 .
MF-AOA asymptotic performance conjecture. In the limit , AMP algorithms such as the MF-AOA achieve a performance of approximately
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 for , while a rigorous asymptotic analysis remains to be established.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.