• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On the complexity of quasiconvex integer minimization problem

Journal of Global Optimization. 2019. Vol. 73. No. 4. P. 761-788.
Chirkov A. Y., Gribanov D., Malyshev D., Pardalos P. M., Veselov S. I., Zolotykh N.

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 log R 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 log R 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.