Name
Abstract | ||
|---|---|---|
Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered particle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable posterior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the difficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler's Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida's Random Energy Model (REM). Furthermore, the derived free energy asymptotics lead to a theoretical justification of a recently introduced concept [3] of Gibbs posterior agreement that measures stability of the Gibbs distributions when the cost function fluctuates due to randomness in the input. This relatively new stability concept may potentially provide a new method to select robust solutions for a large class of optimization problems. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2018.04.015 | Theoretical Computer Science |
Keywords | Field | DocType |
Free energy,Uncertain optimization,Gibbs distribution,Random energy model,Partition function asymptotics,Minimum Bisection,Quadratic Assignment,Information Criterion | Applied mathematics,Discrete mathematics,Boltzmann distribution,Quadratic assignment problem,Random energy model,Principle of maximum entropy,Stable distribution,Asymptotic analysis,Optimization problem,Mathematics,Randomness | Journal |
Volume | ISSN | Citations |
745 | 0304-3975 | 1 |
PageRank | References | Authors |
0.35 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| joachim m buhmann | 1 | 4363 | 730.34 |
| Julien Dumazert | 2 | 2 | 0.71 |
| Alexey Gronskiy | 3 | 7 | 2.15 |
| Wojciech Szpankowski | 4 | 1557 | 192.33 |