Approximating the volume of a truncated relaxation of the independence polytope
<|reference_start|>Approximating the volume of a truncated relaxation of the independence polytope: 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.<|reference_end|>
@article{bencs2024approximating,
    title={Approximating the volume of a truncated relaxation of the independence
  polytope},
    author={Ferenc Bencs, Guus Regts},
    journal={arXiv preprint arXiv:2404.08577},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.08577},
    primaryClass={math.CO cs.DM cs.DS}
}