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