咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >On the complexity of quasiconv... 收藏

On the complexity of quasiconvex integer minimization problem

在 quasiconvex 整数最小化问题的复杂性上

作     者:Chirkov, A. Yu. Gribanov, D. V. Malyshev, D. S. Pardalos, P. M. Veselov, S. I. Zolotykh, N. Yu. 

作者机构:Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia Univ Florida 401 Weil HallPOB 116595 Gainesville FL 32611 USA 

出 版 物:《JOURNAL OF GLOBAL OPTIMIZATION》 (全局最优化杂志)

年 卷 期:2019年第73卷第4期

页      面:761-788页

核心收录:

学科分类:1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基  金:Russian Science Foundation [17-11-01336] Russian Science Foundation [17-11-01336] Funding Source: Russian Science Foundation 

主  题:Nonlinear integer programming Conic functions Quasiconvex functions Quasiconvex polynomials Convex functions Comparison oracle Oracle model Complexity 

摘      要:In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered, assuming that the optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on logR to optimize quasiconvex functions in the ball of radius R using only the comparison oracle. On the other hand, if the optimized function is conic, then we show that there is a polynomial on logR algorithm (the dimension is fixed). We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分