|
This article is cited in 3 scientific papers (total in 3 papers)
Minimax problems of discrete optimization invariant under majority operators
E. V. Vodolazskiia, B. Flachb, M. I. Schlesingera a International Scientific Educational Center, pr. Akademika Glushkova 40, Kiev, 03680, Ukraine
b Czech Technical University in Prague, Zikova 4, Prague, 16636, Czech Republic
Abstract:
A special class of discrete optimization problems that are stated as a minimax modification of the constraint satisfaction problem is studied. The minimax formulation of the problem generalizes the classical problem to realistic situations where the constraints order the elements of the set by the degree of their feasibility, rather than defining a dichotomy between feasible and infeasible subsets. The invariance of this ordering under an operator is defined, and the discrete minimization of functions invariant under majority operators is proved to have polynomial complexity. A particular algorithm for this minimization is described.
Key words:
discrete optimization problem, minimax modification, solution algorithm.
Received: 21.10.2013 Revised: 04.02.2014
Citation:
E. V. Vodolazskii, B. Flach, M. I. Schlesinger, “Minimax problems of discrete optimization invariant under majority operators”, Zh. Vychisl. Mat. Mat. Fiz., 54:8 (2014), 1368–1378; Comput. Math. Math. Phys., 54:8 (2014), 1327–1336
Linking options:
https://www.mathnet.ru/eng/zvmmf10082 https://www.mathnet.ru/eng/zvmmf/v54/i8/p1368
|
Statistics & downloads: |
Abstract page: | 279 | Full-text PDF : | 179 | References: | 50 | First page: | 3 |
|