Ural Mathematical Journal (UMJ)
Not a member yet
157 research outputs found
Sort by
ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE
Get PDFThe Hitting Set Problem (HSP) is the well known extremal problem adopting research interest in the fields of combinatorial optimization, computational geometry, and statistical learning theory for decades. In the general setting, the problem is NP-hard and hardly approximable. Also, the HSP remains intractable even in very specific geometric settings, e.g. for axis-parallel rectangles intersecting a given straight line. Recently, for the special case of the problem, where all the rectangles are unit squares, a polynomial but very time consuming optimal algorithm was proposed. We improve this algorithm to decrease its complexity bound more than 100 degrees of magnitude. Also, we extend it to the more general case of the problem and show that the geometric HSP for axis-parallel (not necessarily unit) squares intersected by a line is polynomially solvable for any fixed range of squares to hit
ON THE BEST APPROXIMATION OF THE DIFFERENTIATION OPERATOR
Get PDFIn this paper we give a solution of the problem of the best approximation in the uniform norm of the differentiation operator of order k by bounded linear operators in the class of functions with the property that the Fourier transforms of their derivatives of order n (0 < k <n) are finite measures. We also determine the exact value of the best constant in the corresponding inequality for derivatives
A GUARANTEED CONTROL PROBLEM FOR A LINEAR STOCHASTIC DIFFERENTIAL EQUATION
Get PDFA problem of guaranteed closed-loop control under incomplete information is considered for a linear stochastic differential equation (SDE) from the viewpoint of the method of open-loop control packages worked out earlier for the guidance of a linear control system of ordinary differential equations (ODEs) to a convex target set. The problem consists in designing a deterministic open-loop control providing (irrespective of a realized initial state from a given finite set) prescribed properties of the solution (being a random process) at a terminal point in time. It is assumed that a linear signal on some number of realizations is observed. By the equations of the method of moments, the problem for the SDE is reduced to an equivalent problem for systems of ODEs describing the mathematical expectation and covariance matrix of the original process. Solvability conditions for the problems in question are written
IILL-POSED PROBLEM OF RECONSTRUCTION OF THE POPULATION SIZE IN THE HUTCHINSON–WRIGHT EQUATION
No full textWe consider an ill-posed problem of reconstruction of the population size in the Hutchinson – Wright Equation. Regularized solutions were constructed on the finite interval of the negative half-line
LINEAR PROGRAMMING AND DYNAMICS
Get PDFIn a Hilbert space we consider the linear boundary value problem of optimal control based on the linear dynamics and the terminal linear programming problem at the right end of the time interval. There is provided a saddle-point method to solve it. Convergence of the method is proved
ON THE COMPLETENESS PROPERTIES OF THE C-COMPACT-OPEN TOPOLOGY ON C(X)
Get PDFThis is a study of the completeness properties of the space Crc(X) of continuous real-valued functions on a Tychonov space X, where the function space has the C-compact-open topology. Investigate the properties such as completely metrizable, Čech-complete, pseudocomplete and almost Čech-complete
ONE-SIDED WIDTHS OF CLASSES OF SMOOTH FUNCTIONS
Get PDFOne-sided widths of the classes of functions Wpr [0,1] in the metric Lq [0,1], 1≤ p, q ≤ ∞, r ≥ 1 are studied. Such widths are defined similarly to Kolmogorov widths with additional constraints on the approximating functions