Discrete Random Walks, DRW'03
Cyril Banderier and Christian Krattenthaler (eds.)
DMTCS Conference Volume AC (2003), pp. 113-126
| author: | David Gamarnik |
|---|---|
| title: | Linear Phase Transition in Random Linear Constraint Satisfaction Problems |
| keywords: | Random K-SAT, Satisfiability Threshold, Linear Programming, Sparse Random Graphs |
| 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 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→∞
, the limit
lim
exists, with high probability. We further extend this
result to maximum weight
n→∞
M(n,c)/n,
b
-matchings also in
G(n,cn)
.
|
| If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. | |
| reference: | David Gamarnik (2003), Linear Phase Transition in Random Linear Constraint Satisfaction Problems, in Discrete Random Walks, DRW'03, Cyril Banderier and Christian Krattenthaler (eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AC, pp. 113-126 |
| bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |
| ps.gz-source: | dmAC0111.ps.gz (56 K) |
| ps-source: | dmAC0111.ps (136 K) |
| pdf-source: | dmAC0111.pdf (152 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.
Automatically produced on Di Sep 27 10:09:17 CEST 2005 by gustedt
