×
Yemets, O. A.; Ust’yan, N. Yu.

Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations. (English. Russian original) Zbl 1142.91380

Cybern. Syst. Anal. 43, No. 6, 848-857 (2007); translation from Kibern. Sist. Anal. 2007, No. 6, 102-114 (2007).
Summary: The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve \((2xn)\)-and \((mx2)\)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems.

Cited in 1 Document

MSC:

91A46 Combinatorial games
91A40 Other game-theoretic models
91A06 \(n\)-person games, \(n>2\)
90C05 Linear programming
90C27 Combinatorial optimization

Keywords:

optimization problem on permutations; antagonistic game; value of game; modified graphical method; linear programming methods; combinatorial optimization
Cite Review PDF
Full Text: DOI

References:

[1] Yu. G. Stoyan and O. O. Yemets, Theory and Methods of Euclidean Combinatorial Optimization [in Ukrainian], ISDO, Kyiv (1993).
[2] Yu. G. Stoyan, S. V. Yakovlev, O. A. Emets, and O. A. Valuiskaya, ”Construction of convex continuations for functions defined on a hypersphere,” Cybern. Syst. Analysis, 34, No. 2, 176–184 (1998). · Zbl 0915.90224 · doi:10.1007/BF02742066
[3] O. A. Emets and A. A. Roskladka, ”Algorithmic solution of two parametric optimization problems on a set of complete combinations,” Cybern. Syst. Analysis, 35, No. 6, 981–986 (1999). · Zbl 0985.90086 · doi:10.1007/BF02742292
[4] O. A. Yemets, L. G. Yevseeva, and N. G. Romanova, ”A mathematical interval model of a combinatorial problem of packing of color rectangles,” Cybern. Syst. Analysis, 37, No. 3, 408–414 (2001). · Zbl 1033.90102 · doi:10.1023/A:1011945928649
[5] O. O. Yemets, L. M. Kolechkina, and S. I. Nedobachii, Analysis of Domains of Definition of Euclidean Combinatorial Optimization Problems on Permutation Sets [in Ukrainian], Polt. Derzh. Tekhn. Univ. Yu. Kondratyuka, Poltava (1999).
[6] O. A. Yemets, ”A truncation method for combinatorial optimization problems,” Ekonomika Mat. Metody, 33, Issue 4, 120–129 (1997).
[7] O. O. Yemets and E. M. Yemets, ”Truncation in linear partially combinatorial problems of Euclidean combinatorial optimization,” Dop. NAN Ukrainy, No. 9, 105–109 (2000). · Zbl 1188.90226
[8] O. A. Yemets and E. M. Yemets, ”Truncations in linear partially combinatorial optimization problems on permutations,” Ekonomika Mat. Metody, 37, No. 1, 118–121 (2001). · Zbl 1098.74591
[9] O. A. Yemets and A. A. Roskladka, ”Solution of a Euclidean combinatorial optimization problem by the dynamic-programming method,” Cybern. Syst. Analysis, 38, No. 1, 117–123 (2002). · Zbl 1033.90103 · doi:10.1023/A:1015504501828
[10] O. A. Emets and T. N. Barbolina, ”Solving linear optimization problems on arrangements by the truncation method,” Cybern. Syst. Analysis, 39, No. 6, 889–896 (2003). · Zbl 1066.90067 · doi:10.1023/B:CASA.0000020230.93910.1d
[11] O. A. Emets and L. N. Kolechkina, ”Solution of optimization problems with fractional-linear objective functions and additional linear constraints on permutations,” Cybern. Syst. Analysis, 40, No. 3, 329–339 (2004). · Zbl 1078.90058 · doi:10.1023/B:CASA.0000041990.90992.bd
[12] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton Univ. Press, Princeton, NJ (1944). · Zbl 0063.05930
[13] E. S. Ventsel’, Elements of Game Theory [in Russian], Fizmatgiz, Moscow (1961). · Zbl 0107.12701
[14] A. V. Krushevskii, Game Theory [in Russian], Vyshcha Shkola, Kyiv (1977).
[15] L. A. Petrosyan, N. A. Zenkevich, and E. A. Semina, Game Theory [in Russian], Vyssh. Shk., Moscow (1998).
[16] Yu. P. Zaichenko, Operations Research [in Russian], Vyshcha Shkola, Kyiv (1979).
[17] T. S. Ferguson, Game Theory, Pt. II. Two-Person Zero-Sum Games, http://www.math.ucla.edu/\(\sim\)tom/Game_Theory/mat.pdf .
[18] I. N. Lyashenko (general editor), E. A. Karagodova, N. V. Chernyshova, and N. Z. Shor, Linear and Nonlinear Programming [in Russian], Vyshcha Shkola, Kyiv (1965).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.