PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
March 2, 2026Discrete & Computational Geometry0 citationsOpen Access

Approximating the Volume of a Truncated Relaxation of the Independence Polytope

FBFerenc BencsGRGuus Regts

Key Points

  • The research aims to develop a polynomial time algorithm for approximating the volume of a truncated relaxation of the independence polytope.
  • Develops a novel algorithm based on a graph polynomial evaluation.
  • Utilizes Barvinok’s interpolation method for volume approximation.
  • Implements improvements over prior quasi-polynomial time algorithms.
  • Successfully approximates the volume in polynomial time.
  • Demonstrates improved efficiency compared to previous methods.
  • The algorithm effectively evaluates graph polynomials.

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Bencs et al. (2026) studied this question.

synapsesocial.com/papers/69a52e64f1e85e5c73bf21a7https://doi.org/10.1007/s00454-026-00824-y
Ask AI
Helpful
Bookmark
Share
View Full Paper