How to Integrate a Polynomial over a Simplex
Skip to main content
eScholarship
Open Access Publications from the University of California

How to Integrate a Polynomial over a Simplex

  • Author(s): Baldoni, Velleda
  • Berline, Nicole
  • De Loera, Jesus
  • Köppe, Matthias
  • Vergne, Michèle
  • et al.

Published Web Location

https://arxiv.org/pdf/0809.2083.pdf
No data is associated with this publication.
Abstract

This paper settles the computational complexity of the problem of integrating a polynomial function f over a rational simplex. We prove that the problem is NP-hard for arbitrary polynomials via a generalization of a theorem of Motzkin and Straus. On the other hand, if the polynomial depends only on a fixed number of variables, while its degree and the dimension of the simplex are allowed to vary, we prove that integration can be done in polynomial time. As a consequence, for polynomials of fixed total degree, there is a polynomial time algorithm as well. We conclude the article with extensions to other polytopes, discussion of other available methods and experimental results.

Item not freely available? Link broken?
Report a problem accessing this item