Saved in:
| Main Authors: | , |
|---|---|
| 格式: | Preprint |
| 出版: |
2024
|
| 主題: | |
| 在線閱讀: | https://arxiv.org/abs/2404.08577 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
書本目錄:
- Answering a question of Gamarnik and Smedira, we give a polynomial time algorithm that approximately computes the volume of a truncation of a relaxation of the independent set polytope, improving on their quasi-polynomial time algorithm. Our algorithm is obtained by viewing the volume as an evaluation of a graph polynomial and we approximate this evaluation using Barvinok's interpolation method.