Name
Abstract | ||
|---|---|---|
Information theoretic properties of large combinatorial systems enable us in better understanding their solution structure and provide insights how to optimize them in a robust manner. In this paper, we revisit the idea of characterizing structural information in solutions for combinatorial problems by information theoretic properties. We provide theorems on analytic expressions of the asymptotic free energy and entropy of solutions with weak dependencies for strongly disordered combinatorial optimization problems, e.g. the sparse Minimum Bisection Problem (sMBP). We prove that the free energy of sMBP with random edge weights exhibits phase transitions equivalent to Derrida's Random Energy Model (REM). Specifically, we analyze the dependency structure between two arbitrary solutions and prove that the influence of correlations on the free energy and the relative entropy vanishes. |
Year | Venue | Field |
|---|---|---|
2018 | 2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) | Statistical physics,Discrete mathematics,Entropy (energy dispersal),Phase transition,Expression (mathematics),Computer science,Random energy model,Dependency structure,Weak solution,Asymptotic analysis,Kullback–Leibler divergence |
DocType | Citations | PageRank |
Conference | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexey Gronskiy | 1 | 7 | 2.15 |
| joachim m buhmann | 2 | 4363 | 730.34 |
| Wojciech Szpankowski | 3 | 1557 | 192.33 |