Phase transitions in integer linear problems

S. Colabrese, D. De Martino, L. Leuzzi, E. Marinari, Journal of Statistical Mechanics: Theory and Experiment 2017 (2017).


Journal Article | Published | English
Author
; ; ;
Department
Abstract
The resolution of a linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density c and the ratio α=N/M between number of variables N and number of constraints M. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane (c, α). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.
Publishing Year
Date Published
2017-09-26
Journal Title
Journal of Statistical Mechanics: Theory and Experiment
Volume
2017
Issue
9
Article Number
093404
ISSN
IST-REx-ID

Cite this

Colabrese S, De Martino D, Leuzzi L, Marinari E. Phase transitions in integer linear problems. Journal of Statistical Mechanics: Theory and Experiment. 2017;2017(9). doi:10.1088/1742-5468/aa85c3
Colabrese, S., De Martino, D., Leuzzi, L., & Marinari, E. (2017). Phase transitions in integer linear problems. Journal of Statistical Mechanics: Theory and Experiment, 2017(9). https://doi.org/10.1088/1742-5468/aa85c3
Colabrese, Simona, Daniele De Martino, Luca Leuzzi, and Enzo Marinari. “Phase Transitions in Integer Linear Problems.” Journal of Statistical Mechanics: Theory and Experiment 2017, no. 9 (2017). https://doi.org/10.1088/1742-5468/aa85c3.
S. Colabrese, D. De Martino, L. Leuzzi, and E. Marinari, “Phase transitions in integer linear problems,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2017, no. 9, 2017.
Colabrese S, De Martino D, Leuzzi L, Marinari E. 2017. Phase transitions in integer linear problems. Journal of Statistical Mechanics: Theory and Experiment. 2017(9).
Colabrese, Simona, et al. “Phase Transitions in Integer Linear Problems.” Journal of Statistical Mechanics: Theory and Experiment, vol. 2017, no. 9, 093404, IOPscience, 2017, doi:10.1088/1742-5468/aa85c3.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar