Approximating the Volume of a Truncated Relaxation of the Independence Polytope
Abstract
Abstract Answering a question of Gamarnik and Smedira [15], 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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Optimization Algorithms Research
Polynomial and algebraic computation
Publication details
- Journal / source
- Discrete & Computational Geometry
- Publisher
- Springer Science and Business Media LLC
- Volume
- 76
- Issue
- 1
- Pages
- 508–525
- Publication date
- 28 February 2026
- Language
- EN