=Paper=
{{Paper
|id=Vol-2098/abstract2
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-2098/abstract2.pdf
|volume=Vol-2098
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-2098/abstract2.pdf</pdf>
<pre>
     On Some Successful Implementations of an
     Asymptotically Optimal Approach for Some
       Hard Discrete Optimization Problems ?

                                Edward Kh. Gimadi1,2
           1
               Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russia
                   2
                     Novosibirsk State University, Novosibirsk, Russia
                                   gimadi@math.nsc.ru


Keywords: asymptotically optimal approach, TSP, metric, Euclidean, cycle
cover problem, matching, algorithm, approximation, k-factor, diameter-bounded
MST.

    In this report we say about some successful implementations of an asymptot-
ically optimal (exact) approach for some discrete optimization problems which
are NP-hard in general case. One of the most popular problems of this kind is the
Travelling Salesman Problem (TSP). It is for the TSP at random instances, this
approach was first implemented by the author jointly with V. Perepelitsa (1969).
    By A. Sedyukov in 1987, the first successful example of constructing asymp-
totically exact algorithm for solving the Euclidean TSP on maximum was pre-
sented.
    In the report, we touch on examples of asymptotically optimal approache
related in time to the present age.
    1. A new modification of a polynomial-time asymptotically optimal algorithm
for the Maximum Traveling Salesman Problem using a decision of the Cycle
Cover Problem as a starting construction.
    2. Construction of polynomial-time asymptotically optimal algorithms for
the m-Peripatetic Salesman Problem (m-PSP) on deterministic and random in-
stances.
    2.1. The m-PSP on maximum in the multi-dimensional Euclidean space.
    2.2. The m-PSP on maximum in the multi-dimensional normed space.
    2.3. The m-PSP on maximum and minimum on random instances with the
finate and infinate carrier of distribution, with different and identical weight
functions of traveling salesman’s routes.
    3. Covering a graph by given number of nonadjacent cycles on some deter-
ministic and random instances.
    4. Finding a connected k-regular spanning subgraphs of maximum weight in
the Euclidean space.
    5. Finding a minimum spanning tree problem with a diameter bounded from
below or above.
?
    This research was supported by Russian Science Foundation (project number 16-11-
    10041).

</pre>