### Article

## Resource characteristics of ways to organize a decision tree in the branch-andboundmethod for the traveling salesmen problem

The resource efficiency of different implementations of the branch-and-bound method for the classical traveling salesman problem depends, inter alia, on ways to organize a search decision tree generated by this method. The classic «time-memory» dilemma is realized herein either by an option of storing reduced matrices at the points of the decision tree, which leads to reduction in the complexity with additional capacity cost, or matrix recalculation for the current node, which leads to an increase in complexity while saving memory. The subject of this paper is an experimental study of temporal characteristics of solving the traveling salesman problem by the branch-and-bound method to identify a real reduction of span time using additional memory in a selected structure of a decision tree. The ultimate objective of the research is to formulate recommendations for implementing the method in practical problems encountered in logistics and business informatics. On the basis of experimental data, this paper shows that both considered options of the classic algorithm for the traveling salesman problem by the branch-and-bound method generate software implementations with an exponential dependence on the execution time of the input length. The experimental results permit us to suggest that the applicability of an additional memory capacity of no more than 1 GB results in a significant (up to five times) reduction of the time span. The estimate of the resulting trend makes it possible to recommend practical application of the software implementation of the branch-and-bound algorithm with storage of matrices - with a really available 16 GB random-access memory and with limitation of the expected average computation time of about one minute on modern personal computers whereby problems having a dimension no more than 70 can be solved exactly.

The tutorial deals with the application of the basic principles of structured programming in complex software systems in the high-level C ++ language, which are demonstrated with meaningful examples.

We propose a novel approach to solving the approximate *k*-nearest neighbor search problem in metric spaces. The search structure is based on a navigable small world graph with vertices corresponding to the stored elements, edges to links between them, and a variation of greedy algorithm for searching. The navigable small world is created simply by keeping old Delaunay graph approximation links produced at the start of construction. The approach is very universal, defined in terms of arbitrary metric spaces and at the same time it is very simple. The algorithm handles insertions in the same way as queries: by finding approximate neighbors for the inserted element and connecting it to them. Both search and insertion can be done in parallel requiring only local information from the structure. The structure can be made distributed. The accuracy of the probabilistic k-nearest neighbor queries can be adjusted without rebuilding the structure.

The performed simulation for data in the Euclidean spaces shows that the structure built using the proposed algorithm has small world navigation properties with 2*log*(*n*) insertion and search complexity at fixed accuracy, and performs well at high dimensionality. Simulation on a CoPHiR dataset revealed its high efficiency in case of large datasets (more than an order of magnitude less metric computations at fixed recall) compared to permutation indexes. Only 0.03% of the 10 million 208-dimensional vector dataset is needed to be evaluated to achieve 0.999 recall (virtually exact search). For recall 0.93 processing speed 2800 queries/s can be achieved on a dual Intel X5675 Xenon server node with Java implementation.

Author describes quantitative methods of optimization in management of different kinds of resources, which can be used within investment projects buildup on the stage of feasibility studies. Particulary, the issue of optimization of re-adjustment time duration is investigated (on the example of cases, when different goods are produced by one tool, but in each discrete time moment only one item can be produced by this tool). The determined model of optimization of re-adjustment time duration is proposed. Also the article contains discription of re-adjustment process optimization under uncertainty and risk.

The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these three types of cost functions we extend this theory from single to set tolerances and the related reverse set tolerances. In particular, we characterize specific values of (reverse) set upper and lower tolerances as positive and infinite, and we present a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present formulas or bounds for computing (reverse) set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. Finally, we give formulas for the minimum and maximum (reverse) set upper and lower tolerances using again their corresponding single tolerance counterparts.

It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the sample. Borders of the interval, which contains 90% of the sample of the logarithm of the complexity, are also given.

The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which defined on mixed multigraph) using the reduction of the original problem into General Travelling Salesman Problem (GTSP). The variants of CPP are pointed out. The mathematical formulations of some problems are presented. The algorithm for reduction the MCPP in multigraph into GTSP is shown. The experimental results of solving MCPP in multigraph through the reduction into GTSP are presented.

Main regularities of the influence of the air adsorbate on the interpretation of images of thin metal films were experimentally determined in the scanning tunneling microscopy (STM). Modification of the surface relief of a thin film of Pt was made in air.Effect of formation of surface structures of 50-100 nm, a cluster of polarized adsorbate molecules by a strong electric field in the electrode gap, was defined. Tunnel voltage and current threshold values of irreversible relief changes was obtained. Technique of local adsorbate removal from the test surface area was developed by pulse contactless interaction of STM electrodes.

We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.

We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.

We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.

The manual is intended for students of Department of computer engineering MIEM HSE. In the textbook based on the courses "Economics of firm" and "the development strategy of the organization." Discusses the key conceptual and methodological issues of the theory and practice of Economics and development planning of the organization. The use of textbooks will enable students: to analyze key performance indicators, and use the tools of strategic analysis with reference to concrete situations in contemporary Russian and international business. Special attention is paid to the methods and systems of information support of the life support functions of business organizations and management methodology of innovation and investment. An Appendix contains source data for analysis of competition in a particular industry.

The paper provides a number of proposed draft operational guidelines for technology measurement and includes a number of tentative technology definitions to be used for statistical purposes, principles for identification and classification of potentially growing technology areas, suggestions on the survey strategies and indicators. These are the key components of an internationally harmonized framework for collecting and interpreting technology data that would need to be further developed through a broader consultation process. A summary of definitions of technology already available in OECD manuals and the stocktaking results are provided in the Annex section.

Over the last two decades national policy makers drew special attention to the implementation of policy tools which foster international cooperation in the fields of science, technology, and innovation. In this paper, we look at cases of Russian-German collaboration to examine the initiatives of the Russian government aimed at stimulating the innovation activity of domestic corporations and small and medium enterprises. The data derived from the interviews with companies’ leaders show positive effects of bilateral innovative projects on the overall business performance alongside with major barriers hindering international cooperation. To overcome these barriers we provide specific suggestions relevant to the recently developed Russian Innovation Strategy 2020.