Linear phase transition in random linear constraint satisfaction problems

• 成果类型: Article
• 署名作者: Gamarnik, D
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-004-0345-z
• 发表日期: 2004
• 页码: 410-440
• 关键词: threshold

摘要

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from 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-->infinity 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-->infinity, 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 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 phi(n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n --> infinity, the limit lim(n-->infinity) phi(n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).