東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Algorithms and generalizations of th...

Harris, David G.

FindBook

Google Book

Amazon

博客來

Algorithms and generalizations of the Lovasz Local Lemma.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Algorithms and generalizations of the Lovasz Local Lemma./
作者:	Harris, David G.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2015,
面頁冊數:	365 p.
附註:	Source: Dissertation Abstracts International, Volume: 77-07(E), Section: B.
Contained By:	Dissertation Abstracts International77-07B(E).
標題:	Theoretical mathematics. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10011544
ISBN:	9781339473567

Algorithms and generalizations of the Lovasz Local Lemma.
Harris, David G.

Algorithms and generalizations of the Lovasz Local Lemma. - Ann Arbor : ProQuest Dissertations & Theses, 2015 - 365 p.

Source: Dissertation Abstracts International, Volume: 77-07(E), Section: B.

Thesis (Ph.D.)--University of Maryland, College Park, 2015.

The Lovasz Local Lemma (LLL) is a cornerstone principle of the probabilistic method for combinatorics. This shows that one can avoid a large of set of "bad-events" (forbidden configurations of variables), provided the local conditions are satisfied. The original probabilistic formulation of this principle did not give efficient algorithms. A breakthrough result of Moser & Tardos led to an framework based on resampling variables which turns nearly all applications of the LLL into efficient algorithms. We extend and generalize the algorithm of Moser & Tardos in a variety of ways.

ISBN: 9781339473567Subjects--Topical Terms:

3173530
Theoretical mathematics.

Algorithms and generalizations of the Lovasz Local Lemma.
LDR:03154nmm a2200361 4500 001 2117626
005 20170530090531.5
008 180830s2015 ||||||||||||||||| ||eng d
020 $a 9781339473567
035 $a (MiAaPQ)AAI10011544
035 $a AAI10011544
040 $a MiAaPQ $c MiAaPQ
100 1 $a Harris, David G. $3 3279407
245 1 0 $a Algorithms and generalizations of the Lovasz Local Lemma.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2015
300 $a 365 p.
500 $a Source: Dissertation Abstracts International, Volume: 77-07(E), Section: B.
500 $a Adviser: Aravind Srinivasan.
502 $a Thesis (Ph.D.)--University of Maryland, College Park, 2015.
520 $a The Lovasz Local Lemma (LLL) is a cornerstone principle of the probabilistic method for combinatorics. This shows that one can avoid a large of set of "bad-events" (forbidden configurations of variables), provided the local conditions are satisfied. The original probabilistic formulation of this principle did not give efficient algorithms. A breakthrough result of Moser & Tardos led to an framework based on resampling variables which turns nearly all applications of the LLL into efficient algorithms. We extend and generalize the algorithm of Moser & Tardos in a variety of ways.
520 $a We show tighter bounds on the complexity of the Moser-Tardos algorithm, particularly its parallel form. We also give a new, faster parallel algorithm for the LLL.
520 $a We show that in some cases, the Moser-Tardos algorithm can converge even though the LLL itself does not apply; we give a new criterion (comparable to the LLL) for determining when this occurs. This leads to improved bounds for k-SAT and hypergraph coloring among other applications.
520 $a We describe an extension of the Moser-Tardos algorithm based on partial resampling, and use this to obtain better bounds for problems involving sums of independent random variables, such as column-sparse packing and packet-routing.
520 $a We describe a variant of the partial resampling algorithm specialized to approximating column-sparse covering integer programs, a generalization of set-cover. We also give hardness reductions and integrality gaps, showing that our partial resampling based algorithm obtains nearly optimal approximation factors.
520 $a We give a variant of the Moser-Tardos algorithm for random permutations, one of the few cases of the LLL not covered by the original algorithm of Moser & Tardos. We use this to develop the first constructive algorithms for Latin transversals and hypergraph packing, including parallel algorithms.
520 $a We analyze the distribution of variables induced by the Moser-Tardos algorithm. We show it has a random-like structure, which can be used to accelerate the Moser-Tardos algorithm itself as well as to cover problems such as MAX k-SAT in which we only partially avoid bad-events.
590 $a School code: 0117.
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Computer science. $3 523869
690 $a 0642
690 $a 0984
710 2 $a University of Maryland, College Park. $b Applied Mathematics and Scientific Computation. $3 1021743
773 0 $t Dissertation Abstracts International $g 77-07B(E).
790 $a 0117
791 $a Ph.D.
792 $a 2015
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10011544