期刊
THEORY OF COMPUTING
卷 13, 期 -, 页码 -出版社
UNIV CHICAGO, DEPT COMPUTER SCIENCE
DOI: 10.4086/toc.2017.v013a017
关键词
Lovasz Local Lemma; Lopsided Lovasz Local Lemma; random permutations; Moser-Tardos algorithm; Latin transversals; rainbow Hamiltonian cycles; strong chromatic number; hypergraph packing
资金
- NSF [CNS-1010789, CCF-1422569]
- Adobe, Inc.
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1422569] Funding Source: National Science Foundation
While there has been significant progress on algorithmic aspects of the Lovasz Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations. The breakthrough algorithm of Moser & Tardos only works in the setting of independent variables, and does not apply in this context. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin transversals: the best general result known here (Bissacot et al., improving on Erdos and Spencer), states that any n x n matrix in which each entry appears at most (27/256)n. times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. We also develop RNC algorithms for Latin transversals, rainbow Hamiltonian cycles, strong chromatic number, and hypergraph packing. In addition to efficiently finding a configuration which avoids bad events, the algorithm of Moser & Tardos has many powerful extensions and properties. These include a well-characterized distribution on the output distribution, parallel algorithms, and a partial resampling variant. We show that our algorithm has nearly all of the same useful properties as the Moser-Tardos algorithm, and present a comparison of this aspect with recent work on the LLL in general probability spaces.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据