Linear Phase Transition in Random Linear Constraint Satisfaction Problem

Details Linear Phase Transition in Random Linear Constraint Satisfaction Problem Linear Phase Transition in Random Linear Constraint Satisfaction Problem

2002-10-31

arxiv.org/abs/math/0210470v2

Mathematics

Probability

26 pages, expanded version

Scientific paper

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 cc*, 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).

Affiliated with

Also associated with

No associations

Rating

Linear Phase Transition in Random Linear Constraint Satisfaction Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Phase Transition in Random Linear Constraint Satisfaction Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Phase Transition in Random Linear Constraint Satisfaction Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-578422