New algorithmic aspects of the local lemma with applications to routing and partitioning

Citation
T. Leighton et al., New algorithmic aspects of the local lemma with applications to routing and partitioning, SIAM J COMP, 31(2), 2001, pp. 626-641
Citations number
25
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
626 - 641
Database
ISI
SICI code
0097-5397(20011011)31:2<626:NAAOTL>2.0.ZU;2-C
Abstract
The Lovasz local lemma ( LLL) is a powerful tool that is increasingly playi ng a valuable role in computer science. The original lemma was nonconstruct ive; a breakthrough of Beck and its generalizations ( due to Alon and Mollo y and Reed) have led to constructive versions. However, these methods do no t capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The rst provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-conge stion routing problems); the second provides new algorithmic results on con structing disjoint paths in graphs. Our results can also be seen as constru ctive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a "gradual rounding" approach.