Deterministic approximation for the volume of the truncated fractional matching polytope
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912022639149056 |
|---|---|
| author | Guo, Heng N, Vishvajeet |
| author_facet | Guo, Heng N, Vishvajeet |
| contents | We give a deterministic polynomial-time approximation scheme (FPTAS) for the volume of the truncated fractional matching polytope for graphs of maximum degree $Δ$, where the truncation is by restricting each variable to the interval $[0,\frac{1+δ}Δ]$, and $δ\le \frac{C}Δ$ for some constant $C>0$. We also generalise our result to the fractional matching polytope for hypergraphs of maximum degree $Δ$ and maximum hyperedge size $k$, truncated by $[0,\frac{1+δ}Δ]$ as well, where $δ\le CΔ^{-\frac{2k-3}{k-1}}k^{-1}$ for some constant $C>0$. The latter result generalises both the first result for graphs (when $k=2$), and a result by Bencs and Regts (2024) for the truncated independence polytope (when $Δ=2$). Our approach is based on the cluster expansion technique. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07283 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic approximation for the volume of the truncated fractional matching polytope Guo, Heng N, Vishvajeet Data Structures and Algorithms Discrete Mathematics Combinatorics We give a deterministic polynomial-time approximation scheme (FPTAS) for the volume of the truncated fractional matching polytope for graphs of maximum degree $Δ$, where the truncation is by restricting each variable to the interval $[0,\frac{1+δ}Δ]$, and $δ\le \frac{C}Δ$ for some constant $C>0$. We also generalise our result to the fractional matching polytope for hypergraphs of maximum degree $Δ$ and maximum hyperedge size $k$, truncated by $[0,\frac{1+δ}Δ]$ as well, where $δ\le CΔ^{-\frac{2k-3}{k-1}}k^{-1}$ for some constant $C>0$. The latter result generalises both the first result for graphs (when $k=2$), and a result by Bencs and Regts (2024) for the truncated independence polytope (when $Δ=2$). Our approach is based on the cluster expansion technique. |
| title | Deterministic approximation for the volume of the truncated fractional matching polytope |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2409.07283 |