کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10333938 689886 2011 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimizing n-variate (n+k)-nomials for small k
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Optimizing n-variate (n+k)-nomials for small k
چکیده انگلیسی
We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our complexity bounds count field operations and inequality checks, and are quadratic in n and the logarithm of a certain condition number. For the special case of n-variate (n+2)-nomials with integer exponents, the log of our condition number is sub-quadratic in the sparse size. The best previous complexity bounds were exponential in the sparse size, even for n fixed. Along the way, we partially extend the theory of Viro diagrams and A-discriminants to real exponents. We also show that, for any fixed δ>0, deciding whether the supremum of an n-variate (n+nδ)-nomial exceeds a given number is NPR-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 16, 1 April 2011, Pages 1457-1469
نویسندگان
, , ,