?
Integer Conic Function Minimization Based on the Comparison Oracle
Let f:R^n→R be a conic function and x_0∈R^n. In this note, we show that the shallow separation oracle for the set K={x∈R^n:f(x)≤f(x_0)} can be polynomially reduced to the comparison oracle of the function f. Combining these results with known results of D. Dadush et al., we give an algorithm with (O(n))^n*logR calls to the comparison oracle for checking the non-emptiness of the set K∩Z^n, where K is included to the Euclidean ball of a radius R. Additionally, we give a randomized algorithm with the expected oracle complexity (O(n))^n*logR for the problem to find an integral vector that minimizes values of f on an Euclidean ball of a radius R. It is known that the classes of convex, strictly quasiconvex functions, and quasiconvex polynomials are included into the class of conic functions. Since any system of conic functions can be represented by a single conic function, the last facts give us an opportunity to check the feasibility of any system of convex, strictly quasiconvex functions, and quasiconvex polynomials by an algorithm with (O(n))^n*logR calls to the comparison oracle of the functions. It is also possible to solve a constraint minimization problem with the considered classes of functions by a randomized algorithm with (O(n))^n*logR expected oracle calls.Let f:R^n→R be a conic function and x_0∈R^n. In this note, we show that the shallow separation oracle for the set K={x∈R^n:f(x)≤f(x_0)} can be polynomially reduced to the comparison oracle of the function f. Combining these results with known results of D. Dadush et al., we give an algorithm with (O(n))^n*logR calls to the comparison oracle for checking the non-emptiness of the set K∩Z^n, where K is included to the Euclidean ball of a radius R. Additionally, we give a randomized algorithm with the expected oracle complexity (O(n))^n*logR for the problem to find an integral vector that minimizes values of f on an Euclidean ball of a radius R. It is known that the classes of convex, strictly quasiconvex functions, and quasiconvex polynomials are included into the class of conic functions. Since any system of conic functions can be represented by a single conic function, the last facts give us an opportunity to check the feasibility of any system of convex, strictly quasiconvex functions, and quasiconvex polynomials by an algorithm with (O(n))^n*logR calls to the comparison oracle of the functions. It is also possible to solve a constraint minimization problem with the considered classes of functions by a randomized algorithm with (O(n))^n*logR expected oracle calls.