T-tetrominoes tiling's Markov chain mixes fast
| Author | Kayibi K.K. |
| Author | Pirzada S. |
| Available date | 2020-01-01T10:25:02Z |
| Publication Date | 2018 |
| Publication Name | Theoretical Computer Science |
| Resource | Scopus |
| ISSN | 0304-3975 |
| Abstract | Korn and Pak (2007) [3] conjectured that there exists a fully polynomial randomized approximation scheme (fpras) for approximating the number of ways of tiling a 4n x 4m rectangular lattice with T-tetrominoes. Using a flow argument, we prove this conjecture in affirmative by showing that the mixing time of an appropriate Markov chain is polynomial in the area of the lattice. - 2017 Elsevier B.V. |
| Sponsor | The authors thank the anonymous referees for their valuable comments and suggestions. We would like to thank Qatar University, Doha, Qatar, and University of Hull, UK, and University of Kashmir, Srinagar, India for providing facilities and support during the preparation of the final form of this paper. The research of second author is supported by SERB-DST , New Delhi under the research project number EMR/2015/001047/MS . |
| Language | en |
| Publisher | Elsevier B.V. |
| Subject | Fpras Mixing time of Markov chains T-tetromino Tiling |
| Type | Article |
| Pagination | Jan-14 |
| Volume Number | 714 |
Check access options
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||
This item appears in the following Collection(s)
-
Mathematics, Statistics & Physics [740 items ]