Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1090/S0025-5718-2010-02378-6 | MATHEMATICS OF COMPUTATION |
Keywords | DocType | Volume |
polynomial time,symbolic computation,computational complexity | Journal | 80 |
Issue | ISSN | Citations |
273 | 0025-5718 | 25 |
PageRank | References | Authors |
2.06 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Velleda Baldoni | 1 | 39 | 4.82 |
| Nicole Berline | 2 | 29 | 3.31 |
| Jesús A. De Loera | 3 | 357 | 42.24 |
| Matthias KöPpe | 4 | 191 | 20.95 |
| Michèle Vergne | 5 | 59 | 8.21 |