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 [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies some results for maximum weight matchings in sparse random graphs G(n, ⌊cn⌋) on n nodes with cn edges, where edges are equipped with randomly generated weights.
- Linear phase transition in random linear constraint satisfaction problems
Recommendations
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer ScienceWe consider random instances of constraint satisfactionproblems where each variable has domain size O(1), eachconstraint is on O(1) variables and the constraints are chosen from a specified distribution. The number of constraints is cn where c is a ...
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
We consider random instances of constraint satisfaction problems (CSPs) where each variable has domain size $O(1)$, each constraint is on $O(1)$ variables, and the constraints are chosen from a specified distribution. The number of constraints is $cn$, where ...
Random constraint satisfaction: Easy generation of hard (satisfiable) instances
In this paper, we show that the models of random CSP instances proposed by Xu and Li [K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12 (2000) 93-103; K. Xu, W. Li, Many hard ...
Comments