Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2407.04989 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913419299389440 |
|---|---|
| author | He, Kun Li, Zhidan Qiu, Guoliang Zhang, Chihao |
| author_facet | He, Kun Li, Zhidan Qiu, Guoliang Zhang, Chihao |
| contents | For an integer $b\ge 0$, a $b$-matching in a graph $G=(V,E)$ is a set $S\subseteq E$ such that each vertex $v\in V$ is incident to at most $b$ edges in $S$. We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of $b$-matchings in graphs with bounded degrees. Our FPTAS also applies to a broader family of counting problems, namely Holant problems with log-concave signatures. Our algorithm is based on Moitra's linear programming approach (JACM'19). Using a novel construction called the extended coupling tree, we derandomize the coupling designed by Chen and Gu (SODA'24). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04989 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | FPTAS for Holant Problems with Log-Concave Signatures He, Kun Li, Zhidan Qiu, Guoliang Zhang, Chihao Data Structures and Algorithms For an integer $b\ge 0$, a $b$-matching in a graph $G=(V,E)$ is a set $S\subseteq E$ such that each vertex $v\in V$ is incident to at most $b$ edges in $S$. We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of $b$-matchings in graphs with bounded degrees. Our FPTAS also applies to a broader family of counting problems, namely Holant problems with log-concave signatures. Our algorithm is based on Moitra's linear programming approach (JACM'19). Using a novel construction called the extended coupling tree, we derandomize the coupling designed by Chen and Gu (SODA'24). |
| title | FPTAS for Holant Problems with Log-Concave Signatures |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.04989 |