De flesta verkliga kombinatoriska optimeringsproblem påverkas av buller i ingångsdata, vilket beter sig i den höga bullergränsen som stora oordnade partikelsystem, t.ex. Spinnglasögon eller slumpmässiga nätverk. På grund av osäkerhet i inmatningen bör optimering av sådana oordnade fall leda till stabila bakre fördelningar av lösningar som är beroende av den bullriga inmatningsinstansen. Den maximala entropi principen anger att den mest stabila fördelningen med tanke på bullerpåverkan definieras av Gibbs distribution och det kännetecknas av den fria energin. I detta papper ger vi först rigorösa asymptotiker av det svåra problemet att beräkna den fria energin för två kombinatoriska optimeringsproblem, nämligen det glesa minimala bisektionsproblemet (sMBP) och Lawlers Quadratic Inlämningsproblem (LQAP). Vi bevisar att båda problemen uppvisar fasövergångar motsvarande det diskontinuerliga beteendet hos Derridas slumpmässiga energimodell (REM). Dessutom leder den härledda fria energiasymptotiken till en teoretisk motivering av ett nyligen infört koncept (Buhmann, 2010) av Gibbs senare avtal som mäter stabiliteten hos Gibbs distributioner när kostnadsfunktionen varierar på grund av slumpmässighet i inmatningen. Detta relativt nya stabilitetskoncept kan potentiellt ge en ny metod för att välja robusta lösningar för en stor klass av optimeringsproblem.
Nyligen, REF bevisa rigorösa asymptotik av PA på två typiska kombinatoriska problem: Sparse minimum bisektion och Lawlers kvadratiska uppdrag problem.
Posterior agreement for large parameter-rich optimization problems
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}