國立虎尾科技大學 |

Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing./
Author:	Frishberg, Daniel.
Description:	1 online resource (169 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-02, Section: B.
Contained By:	Dissertations Abstracts International85-02B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798380130677

Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing.
Frishberg, Daniel.

Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing. - 1 online resource (169 pages)

Source: Dissertations Abstracts International, Volume: 85-02, Section: B.

Thesis (Ph.D.)--University of California, Irvine, 2023.

Includes bibliographical references

We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n3 log3 n), the first progress since McShine and Tetali's O(n5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Ω(1/( √n log n)) and O(1/ √n) -asymptotically tight up to an O(log n) factor-for the expansion of the associahedron graph Kn-the first o(1) expansion result for this graph. We show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k ≥ 4, and a treewidth result for the flip graph on n x n lattice triangulations.We show that the hardcore Glauber dynamics-a random walk on the independent sets of an input graph-mixes rapidly in graphs of bounded treewdith for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets and b-edge covers (for fixed b ≥ 1 and λ > 0) in bounded-treewidth graphs, and for Markov chains on the b-matchings (for fixed b ≥ 1 and λ > 0), the maximal independent sets, and the maximal b-matchings of a graph (for fixed b ≥ 1), in graphs of bounded carving width.To obtain these results, we introduce a decomposition framework for showing rapid Markov chain mixing. This framework is a purely combinatorial analogue that in some settings gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798380130677Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

AssociahedronIndex Terms--Genre/Form:

554714
Electronic books.

Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing.
LDR:02905ntm a22004097 4500 001 1143610
005 20240517104611.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798380130677
035 $a (MiAaPQ)AAI30524670
035 $a AAI30524670
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Frishberg, Daniel. $3 1468348
245 1 0 $a Flow-Based Decomposition for Geometric and Combinatorial Markov Chain Mixing.
264 0 $c 2023
300 $a 1 online resource (169 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-02, Section: B.
500 $a Advisor: Eppstein, David.
502 $a Thesis (Ph.D.)--University of California, Irvine, 2023.
504 $a Includes bibliographical references
520 $a We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n3 log3 n), the first progress since McShine and Tetali's O(n5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Ω(1/( √n log n)) and O(1/ √n) -asymptotically tight up to an O(log n) factor-for the expansion of the associahedron graph Kn-the first o(1) expansion result for this graph. We show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k ≥ 4, and a treewidth result for the flip graph on n x n lattice triangulations.We show that the hardcore Glauber dynamics-a random walk on the independent sets of an input graph-mixes rapidly in graphs of bounded treewdith for all fixed values of the standard parameter λ > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets and b-edge covers (for fixed b ≥ 1 and λ > 0) in bounded-treewidth graphs, and for Markov chains on the b-matchings (for fixed b ≥ 1 and λ > 0), the maximal independent sets, and the maximal b-matchings of a graph (for fixed b ≥ 1), in graphs of bounded carving width.To obtain these results, we introduce a decomposition framework for showing rapid Markov chain mixing. This framework is a purely combinatorial analogue that in some settings gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Mathematics. $3 527692
650 4 $a Applied mathematics. $3 1069907
653 $a Associahedron
653 $a Glauber dynamics
653 $a Markov chain
653 $a Mixing
653 $a Projection-restriction
653 $a Triangulations
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0405
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Irvine. $b Computer Science. $3 1179555
773 0 $t Dissertations Abstracts International $g 85-02B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30524670 $z click for full text (PQDT)