Back to Search
Start Over
Approximating the volume of a truncated relaxation of the independence polytope
- Publication Year :
- 2024
-
Abstract
- 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.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2404.08577
- Document Type :
- Working Paper