THEORETICAL ASSESSMENTS OF THE COMPLEXITY OF ALGORITHMS OF ITERATIVE METHODS OF THE BROWN-ROBINSON TYPE FOR SOLVING COMBINATORY OPTIMIZATION PROBLEMS OF THE GAME TYPE

Abstract

Game-type combinatorial optimization problems are one of the most important categories of problems in the field of game theory and optimization. They cover a wide range of issues, from resource allocation to strategic planning in conflict. Iterative methods, in particular the Brown-Robinson method, are classic approaches to solving such problems. The need to solve game-type combinatorial optimization problems with multiple permutations and placements emphasizes the importance of studying the possibility of modifying existing methods and assessing their complexity. An extension of the iterative method for game-type combinatorial optimization problems with various combinatorial configurations is performed. The article begins with a description of algorithms of Brown-Robinson type methods used to solve combinatorial optimization problems of game type on sets of permutations and placements. Further, the main emphasis is placed on theoretical estimates of the complexity of these algorithms. The number of iterations required to achieve the optimal solution is considered, as well as the asymptotic complexity of algorithms depending on the dimension of the problem and parameters. The conditions of convergence of algorithms are studied. Complexity bounds are defined for worst-case scenarios, where algorithms can exhibit maximum complexity. For iterative methods of the Brown-Robinson type, which solve combinatorial optimization problems of the game type with permutation constraints imposed on the strategies of both players, and for solving game problems with placement constraints on the strategies of one player. obtained theoretical estimates of complexity, formulated in the form of theorems. The research results confirm that iterative methods of the Brown-Robinson type are effective tools for solving combinatorial game-type optimization problems. However, their computational complexity largely depends on the specifics of the problem. Further research in this direction can significantly improve the understanding and application of these methods in practice, contributing to the development of game theory and combinatorial optimization.