Skip to Main content Skip to Navigation
Conference papers

Linear Phase Transition in Random Linear Constraint Satisfaction Problems

Abstract : 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 are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition,when $n→∞$ and $m=cn$ for a constant $c$. Namely, there exists a critical value $c^*$ such that, when $c < c^*$, the problem is feasible or is asymptotically almost feasible, as $n→∞$, but, when $c > c^*$, the "distance" to feasibility is at least a positive constant independent of $n$. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [1992, 2000], Aldous and Steele [2003], Steele [2002] and martingale techniques. By exploiting a linear programming duality, our theorem impliesthe 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 $\mathcal{M}(n,c)$ denote maximum weight matching in $G(n, cn)$. We prove that when $c$ is a constant and $n→∞$, the limit $lim_{n→∞} \mathcal{M}(n,c)/n$, exists, with high probability. We further extend this result to maximum weight b-matchings also in $G(n,cn)$.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183947
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 9:08:56 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:38:32 AM

File

dmAC0111.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

David Gamarnik. Linear Phase Transition in Random Linear Constraint Satisfaction Problems. Discrete Random Walks, DRW'03, 2003, Paris, France. pp.113-126, ⟨10.46298/dmtcs.3351⟩. ⟨hal-01183947⟩

Share

Metrics

Record views

125

Files downloads

584