Linear Phase Transition in Random Linear Constraint Satisfaction Problems

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 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)$.
Type de document :
Communication dans un congrès
Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.113-126, 2003, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01183947
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:08:56
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:38:32

Fichier

dmAC0111.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01183947, version 1

Collections

Citation

David Gamarnik. Linear Phase Transition in Random Linear Constraint Satisfaction Problems. Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.113-126, 2003, DMTCS Proceedings. 〈hal-01183947〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

62