@Article{Vodolazskiy:CMMP2014, IS = { zkontrolovano 03 Jan 2015 }, UPDATE = { 2014-12-19 }, author = {Vodolazskii, Evgenenij. V. and Flach, Boris and Schlesinger, Michail I.}, title = {Minimax Problems of Discrete Optimization Invariant under Majority Operators}, journal = {Computational Mathematics and Mathematical Physics}, year = {2014}, month = {August}, volume = {54}, number = {8}, pages = {1327-1336}, authorship = {35-30-35}, affiliation = {NULL-13133-NULL}, publisher = {Pleiades Publishing Ltd.}, address = {Moscow,Russian Federation}, issn = {0965-5425}, keywords = {discrete optimization problem, minimax modification, solution algorithm}, doi = {10.1134/S0965542514080144}, project = {GACR P202/12/2071}, annote = {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.}, }