کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9501279 | 1338396 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of integer quasiconvex polynomial optimization
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
آنالیز ریاضی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We design an algorithm solving this problem that belongs to the time-complexity class O(s)·lO(1)·dO(n)·2O(n3), where d⩾2 is an upper bound for the total degree of the polynomials involved and l denotes the maximum binary length of all coefficients. The algorithm is polynomial for a fixed number n of variables and represents a direct generalization of Lenstra's algorithm [Math. Oper. Res. 8 (1983) 538-548] in integer linear optimization. In the considered case, our complexity-result improves the algorithm given by Khachiyan and Porkolab [Discrete Comput. Geom. 23 (2000) 207-224] for integer optimization on convex semialgebraic sets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 21, Issue 4, August 2005, Pages 543-556
Journal: Journal of Complexity - Volume 21, Issue 4, August 2005, Pages 543-556
نویسندگان
Sebastian Heinz,