David Gamarnik - Linear Phase Transition in Random Linear Constraint Satisfaction Problems

dmtcs:3351 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) - https://doi.org/10.46298/dmtcs.3351
Linear Phase Transition in Random Linear Constraint Satisfaction Problems

Authors: David Gamarnik

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)$.

Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: May 10, 2017
Keywords: Sparse Random Graphs,Random K-SAT,Satisfiability Threshold,Linear Programming,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]