Journal
MATHEMATICS OF COMPUTATION
Volume 80, Issue 273, Pages 297-325Publisher
AMER MATHEMATICAL SOC
DOI: 10.1090/S0025-5718-2010-02378-6
Keywords
-
Categories
Funding
- NSF [DMS-0608785]
- CRM
- Direct For Mathematical & Physical Scien [0914873] Funding Source: National Science Foundation
- Division Of Mathematical Sciences [0914873] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper starts by settling 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 explore our algorithms with some experiments. We conclude the article with extensions to other polytopes and discussion of other available methods.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available