Minimax problems of discrete optimization invariant under majority operators

作者：Vodolazskii E V^*; Flach B; Schlesinger M I

来源：Computational Mathematics and Mathematical Physics, 2014, 54(8): 1327-1336.

DOI：10.1134/S0965542514080144

• discrete optimization problem
• minimax modification
• solution algorithm

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.

• 出版日期2014-8