Approximating the Volume of a Truncated Relaxation of the Independence Polytope
| Authors | |
|---|---|
| Publication date | 07-2026 |
| Journal | Discrete and Computational Geometry |
| Volume | Issue number | 76 | 1 |
| Pages (from-to) | 508-525 |
| Organisations |
|
| 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. |
| Document type | Article |
| Language | English |
| Published at |
https://doi.org/10.1007/s00454-026-00824-y
(Final published version)
|
| Other links | |
| Downloads |
Approximating the Volume of a Truncated Relaxation of the Independence Polytope
(Final published version)
|
| Permalink to this page | |