Search

Recently classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. Recently the lower bound $3^{n-1}\log (2 \rho-1)$ for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some $n$-dimensional ball with radius $\rho$ was obtained. But the problem of the existence of a polynomial (in $\log\rho$ for fixed $n$) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses $2^{O(n^2 \log n)} \log \rho$ calls to the comparison oracle and has $2^{O(n^2 \log n)} \mbox{poly }(\log \rho)$ bit complexity.

We study the proximity of the optimal value of the m-dimensional knapsack problem to the optimal value of that problem with the additional restriction that only one type of items is allowed to include in the solution. We derive exact and asymptotic formulas for the precision of such approximation, i.e. for the infinum of the ratio of the optimal value for the objective functions of the problem with the cardinality constraint and without it. In particular, we prove that the precision tends to 0.59136.../m if n tends to infinity and m is fixed. Also, we give the class of the worst multi-dimensional knapsack problems for which the bound is attained. Previously, similar results were known only for the case m=1., Comment: 7 pages submitted to MOTOR 2020

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 in the paper, assuming that an 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 integer radius $R$ using only the comparison oracle. On the other hand, if an optimized function is conic, then we show that there is a polynomial on $\log R$ algorithm. 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., Comment: Some new proofs have been added. Some fixes are done

An integer point in a polyhedron is called irreducible iff it is not the midpoint of two other integer points in the polyhedron. We prove that the number of irreducible integer points in $n$-dimensional polytope with radius $k$ given by a system of $m$ linear inequalities is at most $O(m^{\lfloor\frac{n}{2}\rfloor}\log^{n-1} k)$ if $n$ is fixed. Using this result we prove the hypothesis asserting that the teaching dimension in the class of threshold functions of $k$-valued logic in $n$ variables is $\Theta(\log^{n-2} k)$ for any fixed $n\ge 2$., Comment: 24 pages, 4 figures

The common feature of sheared flows of an ideal fluid and plasma in magnetic field is the Kelvin-Helmholtz instability. This instability is described by identical equations in mentioned two cases. The wave equation for the eigenmodes in the plasma obtained by the kinetic method in the long-wave limit coincides with the Rayleigh equation known for an ideal fluid. Velocity profile with a transition layer of finite width is considered. Odd modes are investigated. Localized velocity shear layer is the source of perturbations propagating beyond the transition layer. The conditions of localization of the modes are studied., Comment: 8 pages, 6 figures

Electrostatic drift instabilities driven by ion and electron temperature gradients (ITG and ETG instabilities) are considered for the ranges of perpendicular wave number values from the inverse ion thermal gyroradius up to the electron thermal gyroradius. The analysis is carried out in the framework of the local kinetic approach. Scaling laws for instability parameters are presented. These scaling laws can be used as a basis of collisionless plasma transport rates in magnetic traps with purely poloidal magnetic field topology., Comment: 5 pages, 5 figures

We consider the bremsstrahlung of electrons of fully ionized plasma. Electron energy range extends from a few hundred electron volts before the extreme relativistic energies of several MeV. The results of calculations of effective slow-down rate of a single electron and the power emission from a volume of the plasma with Maxwellian electrons. At relativistic energies, the Born approximation yields highly accurate results. Correction to the Born approximation are considered for low-energy regimes. In the high-energy regimes numerical results are close to extreme relativistic analytic results. The formulas are suggested that approximate the results of numerical calculations., Comment: 6 pages, 3 figures, ver. 2 with corrected typos