A monotone iterative method for solving the combinatorial game-type optimization problems on permutations

TitleA monotone iterative method for solving the combinatorial game-type optimization problems on permutations
Publication TypeJournal Article
Year of Publication2014
AuthorsIemets, OO, Olkhovskaya, EV
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.15407/dopovidi2014.08.048
Issue8
SectionInformation Science and Cybernetics
Pagination48-52
Date Published8/2014
LanguageUkrainian
Abstract

A monotone iterative method of searching for the game price for solving the combinatorial game-type optimization problems on permutations with restrictions on the strategy of one player is proposed. The monotonous iterative method allows one to quickly get the price value for a game with the specified accuracy and the optimal strategy for the first player. Moreover, the number of steps of the method weakly depends on the dimension of the problem.

Keywordscombinatorial optimization problems, monotone iterative method
References: 

1. Emets O. A., Ustian N. Yu. Kibernetika i sist. analiz, 2007, No 6: 103–114 (in Russian).
2. Emets O. A., Ustian N. Yu. Nauk. visti NTUU “KPI”, 2007, No 3: 47–52 (in Ukrainian).
3. Emets O. A., Ustian N. Yu. Nauk. visti NTUU “KPI”, 2008, No 3: 5–10 (in Ukrainian).
4. Emets O. A., Olkhovskaya E. V. Probl. upravleniia i informatiki, 2011, No 3: 69–78 (in Russian).
5. Sadovskiy A. L. Dokl. AN USSR, 1978, 238, No 3: 538–540 (in Russian).
6. Stoian Yu. G., Emets O. O. Theory and methods of Euclidean combinatorial optimization, Kyiv: Int-t systemn. doslidzhen osvity, 1993 (in Ukrainian).