Linear Phase Transition in Random Linear Constraint Satisfaction Problem
| dc.creator | Gamarnik, David | |
| dc.date | 2002-10-31 | |
| dc.date | 2003-05-14 | |
| dc.date.accessioned | 2026-07-07T04:52:30Z | |
| dc.date.available | 2026-07-07T04:52:30Z | |
| dc.description | Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints C on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from C also uniformly at random. This procedure is repeated m times independently. We ask the following question: is the resulting linear programming problem feasible? We show that the feasibility property experiences a linear phase transition, when n diverges to infinity and m=cn for some constant c. Namely, there exists a critical value c* such that, when c<c*, the system is feasible or is asymptotically almost feasible, as n increases, but, when c>c*, the "distance" from feasibility is at least a positive constant independent of n. Our results are obtained using powerful local weak convergence methods developed by Aldous and Steele. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let M(n,c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n\to\infty, the limit \lim_n M(n,c)/n exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n,cn). | |
| dc.description | 26 pages, expanded version | |
| dc.identifier | https://arxiv.org/abs/math/0210470 | |
| dc.identifier | http://arxiv.org/abs/math/0210470 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/65487 | |
| dc.subject | Probability | |
| dc.subject | Mathematical Physics | |
| dc.subject | 60C05 ;60G42;60K35;82B20;82B26 | |
| dc.title | Linear Phase Transition in Random Linear Constraint Satisfaction Problem | |
| dc.type | text |