|
|
 |
• Содержание выпуска •
• Mathematical Foundations of Programming •
• Methods for Optimal Control and Control Theory •
• Artificial Intelligence, Intelligence Systems, Neural Networks •
• Supercomputing Software and Hardware •
Mathematical Foundations of Programming
Responsible for the Section: doctor of physico-mathematical Sciences
Nikolay Nepeivoda
On the left: assigned number of the paper, submission date, the number
of A5 pages contained in the paper, and the reference to the full-text
PDF
/r1/pdf.jpg) .
|
Article #
17_2020
14
p.
/r2/pdf.jpg)
PDF |
submitted on 11th Apr 2020 displayed on
website on 09th Oct
2020
Victor V.
Burkhovetskiy
Optimization and Parallelization of Simplified Balas’ and
Christofides’ Algorithm for the Traveling Salesman Problem
The paper describes an exact parallel algorithm for the
traveling salesman problem based on simplified Balas’ and
Christofides’ algorithm, its optimization, and improvements in its
parallel efficiency. Due to the new method of passing tasks between
parallel threads, the algorithm solves, on average, instances with
3000 nodes (with random edge weights) in 1 minute, and instances
with 10000 nodes in 50 minutes. The algorithm can solve instances
with more than 3000 nodes due to the memory usage optimization
introduced in this paper. (In Russian).
Key words: branch-and-bound, parallel computing, traveling
salesman problem, tree traversal, memory optimization.
|
|
article citation |
http://psta.psiras.ru/read/psta2020_4_3-16.pdf |
|
DOI |
http://doi.org/10.25209/2079-3316-2020-11-4-3-16 |
|
Article #
21_2020
25
p.
PDF |
submitted on 17th Oct 2020 displayed on
website on 29th Dec
2020
Sergej V.
Znamenskij
Local competing in interpolation problems
A simple example illustrates the insufficiency of the known
approaches to interpolation in the problem of recovering a function
from a few given specific values that clearly convey the form.
A local choice between polynomial and rational local interpolants,
which minimizes the local interpolant’s errors at the nearest
external nodes from one or different sides, complements the known
approaches. It combines the extreme computational simplicity of
local interpolants with the thorought selection of them.
The principles of constructing the algorithm are formulated in
general terms for mappings of metric spaces. They provide accurate
(with rare exceptions) reconstruction of mappings that locally
coincide with some of the given possible interpolants.
In the one-dimensional case, the two-stage algorithm guarantees the
continuity of the interpolant and accurately reconstructs
(1) polynomials of small degree,
(2) simple rational functions with a linear denominator,
(3) broken lines of long links with knots at the ends
when these requirements do not contradict each other. An additional
parameter allows you to replace the exact restoration of polylines
with the required smoothness of interpolation. (In Russian).
Key words: polynomial interpolation, rational interpolation,
spline interpolation,
adaptive spline, local algorithm, metric space, explicit formula, a
set of patterns.
|
|
article citation |
http://psta.psiras.ru/read/psta2020_4_73-97.pdf |
|
DOI |
https://doi.org/10.25209/2079-3316-2020-11-4-73-97 |
|
Article #
22_2020
24
p.
PDF |
submitted on 17th Oct 2020 displayed on
website on 29th Dec
2020
Sergej V.
Znamenskij
Local competing in interpolation problems
A simple example illustrates the insufficiency of the known
approaches to interpolation in the problem of recovering a function
from a few given specific values that clearly convey the form.
A local choice between polynomial and rational local interpolants,
which minimizes the local interpolant’s errors at the nearest
external nodes from one or different sides, complements the known
approaches. It combines the extreme computational simplicity of
local interpolants with the thorought selection of them.
The principles of constructing the algorithm are formulated in
general terms for mappings of metric spaces. They provide accurate
(with rare exceptions) reconstruction of mappings that locally
coincide with some of the given possible interpolants.
In the one-dimensional case, the two-stage algorithm guarantees the
continuity of the interpolant and accurately reconstructs
(1) polynomials of small degree,
(2) simple rational functions with a linear denominator,
(3) broken lines of long links with knots at the ends
when these requirements do not contradict each other. An additional
parameter allows you to replace the exact restoration of polylines
with the required smoothness of interpolation.
Key words: polynomial interpolation, rational interpolation,
spline interpolation,
adaptive spline, local algorithm, metric space, explicit formula, a
set of patterns.
|
|
article citation |
http://psta.psiras.ru/read/psta2020_4_99-122.pd |
|
DOI |
https://doi.org/10.25209/2079-3316-2020-11-4-99-122 |
• Содержание выпуска •
• Mathematical Foundations of Programming •
• Methods for Optimal Control and Control Theory •
• Artificial Intelligence, Intelligence Systems, Neural Networks •
• Supercomputing Software and Hardware •
|
