We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin-Kernighan-Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show that using an approximate solution found with the Lin-Kernighan-Helsgaun algorithm can signi cantly reduce the search time for the exact solution to the traveling salesman problem using the branch-and-bound method for problems from a certain class. We construct a prediction of the search time for the exact solution by the branch-and-bound method and by the hybrid algorithm. A computational experiment has shown that the proportion of tasks solved faster by the hybrid algorithm than by the branch-and-bound method grows with increasing problem dimension.
Для повышения надежности доставки данных в сетях Wi-Fi станции могут резервировать для своих передач периодические интервалы времени одинаковой длительности, в течение которых они имеют право передавать, а соседние с ними станции такого права не имеют. При этом возникает задача выбора параметров резервируемых интервалов, которые гарантировали бы выполнение требований к качеству обслуживания передаваемых данных при наименьшем объеме зарезервированного канального времени. Рассматривается процесс передачи данных в периодических интервалах с использованием политики блочного квитирования, позволяющей сократить накладные расходы за счет квитирования множества пакетов с помощью одного служебного сообщения. Предлагается метод математического моделирования такой передачи.
The paper studies the problem of achieving consensus in multi-agent systems in the case where the dependency digraph Γ has no spanning in-tree. We consider the regularization protocol that amounts to the addition of a dummy agent (hub) uniformly connected to the agents. The presence of such a hub guarantees the achievement of an asymptotic consensus. For the “evaporation” of the dummy agent, the strength of its influences on the other agents vanishes, which leads to the concept of latent consensus. We obtain a closed-form expression for the consensus when the connections of the hub are symmetric; in this case, the impact of the hub upon the consensus remains fixed. On the other hand, if the hub is essentially influenced by the agents, whereas its influence on them tends to zero, then the consensus is expressed by the scalar product of the vector of column means of the Laplacian eigenprojection of Γ and the initial state vector of the system. Another protocol, which assumes the presence of vanishingly weak uniform background links between the agents, leads to the same latent consensus.
Robust stability test is formulated and the methodology of its use in the robust control system design is presented. The paper makes a contribution to the existing approaches to solution of this class of problems.