A PTAS for the minimization of polynomials of fixed degree over the simplex
Lists
Only you see this
Abstract
We consider the problem of computing the minimum value p min taken by a polynomial p(x) of degree d over the standard simplex #. This is an NP-hard problem already for degree d = 2. For any integer k 1, by minimizing p(x) over the set of rational points in # with denominator k, one obtains a hierarchy of upper bounds p #(k) converging to p min as k -# #.
BibTeX
@article{klerk2006ptas,
author = {Etienne de Klerk and Monique Laurent and Pablo A. Parrilo},
title = {{A PTAS for the minimization of polynomials of fixed degree over the simplex}},
journal = {Theoretical Computer Science},
year = {2006},
doi = {10.1016/j.tcs.2006.05.011},
}Loading related content...