Geodesic
Minimax problems of discrete optimization invariant under majority operators
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 8, pp. 1368-1378 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{ZVMMF_2014_54_8_a11,
     author = {E. V. Vodolazskii and B. Flach and M. I. Schlesinger},
     title = {Minimax problems of discrete optimization invariant under majority operators},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1368--1378},
     year = {2014},
     volume = {54},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2014_54_8_a11/}
}
TY  - JOUR
AU  - E. V. Vodolazskii
AU  - B. Flach
AU  - M. I. Schlesinger
TI  - Minimax problems of discrete optimization invariant under majority operators
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2014
SP  - 1368
EP  - 1378
VL  - 54
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2014_54_8_a11/
LA  - ru
ID  - ZVMMF_2014_54_8_a11
ER  - 
%0 Journal Article
%A E. V. Vodolazskii
%A B. Flach
%A M. I. Schlesinger
%T Minimax problems of discrete optimization invariant under majority operators
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2014
%P 1368-1378
%V 54
%N 8
%U http://geodesic.mathdoc.fr/item/ZVMMF_2014_54_8_a11/
%G ru
%F ZVMMF_2014_54_8_a11
E. V. Vodolazskii; B. Flach; M. I. Schlesinger. Minimax problems of discrete optimization invariant under majority operators. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 54 (2014) no. 8, pp. 1368-1378. http://geodesic.mathdoc.fr/item/ZVMMF_2014_54_8_a11/

[1] Bulatov A., Jeavons P., Tractable constraints closed under a binary operation, Technical Report PGR-TR-12-00, Oxford University Computing Laboratory, 2000

[2] Bulatov A., “Tractable conservative constraint satisfaction problems”, Proc. 18th Annual IEEE Symposium on Logic in Computer Science, LICS'03 (Washington, DC, USA, 2003)

[3] Bulatov A., “Complexity of conservative constraint satisfaction problems”, ACM Trans. Comput. Logic, 12:4 (July 2011), 24:1–24:66 | DOI

[4] Rossi F., van Beek P., Walsh T., Handbook of Constraint Programming. Foundation of Artificial Intelligence, Elsevier Science, 2006

[5] Schlesinger M. I., Flach B., “Some solvable subclasses of structural recognition problems”, Czech Pattern Recognition Workshop (2000)

[6] Scherbina O. A., “Udovletvorenie ogranichenii i programmirovanie v ogranicheniyakh”, Intellektualnye sistemy, 15:1–4 (2011), 53–170