Deterministic counting from coupling independence
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909565952458752 |
|---|---|
| author | Chen, Xiaoyu Feng, Weiming Guo, Heng Zhang, Xinyuan Zou, Zongrui |
| author_facet | Chen, Xiaoyu Feng, Weiming Guo, Heng Zhang, Xinyuan Zou, Zongrui |
| contents | We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for $q$-colourings on graphs of bounded maximum degree $Δ\ge 3$, when $q\ge (11/6-\varepsilon_0)Δ$ for some small $\varepsilon_0\approx 10^{-5}$, or when $Δ\ge 125$ and $q\ge 1.809Δ$, and on graphs with sufficiently large (but constant) girth, when $q\geqΔ+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23225 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic counting from coupling independence Chen, Xiaoyu Feng, Weiming Guo, Heng Zhang, Xinyuan Zou, Zongrui Data Structures and Algorithms Discrete Mathematics We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for $q$-colourings on graphs of bounded maximum degree $Δ\ge 3$, when $q\ge (11/6-\varepsilon_0)Δ$ for some small $\varepsilon_0\approx 10^{-5}$, or when $Δ\ge 125$ and $q\ge 1.809Δ$, and on graphs with sufficiently large (but constant) girth, when $q\geqΔ+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively. |
| title | Deterministic counting from coupling independence |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2410.23225 |