Abstract. A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists.
Keywords: discrete optimization, minimax problems, labeling, invariants, polymorphisms.
1 International Scientific and Training Center of Information Technologies and Systems, National Academy of
Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kyiv, Ukraine,
e-mail: schles@irtc.org.ua.
2 Center of Machine Vision, Czech Technical University in Prague, Prague, Czech Republic,
e-mail: flachbor@cmp.felk.cvut.cz.
3 International Scientific and Training Center of Information Technologies and Systems, National Academy of
Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kyiv, Ukraine,
e-mail: waterlaz@gmail.com.