Geodesic
Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements
Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 95-104 
O. A. Emets; T. N. Barbolina. Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements. Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 95-104. http://geodesic.mathdoc.fr/item/DM_2007_19_1_a11/
@article{DM_2007_19_1_a11,
     author = {O. A. Emets and T. N. Barbolina},
     title = {Classes of lexicographic equivalence in {Euclidean} combinatorial optimisation on arrangements},
     journal = {Diskretnaya Matematika},
     pages = {95--104},
     year = {2007},
     volume = {19},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2007_19_1_a11/}
}
TY  - JOUR
AU  - O. A. Emets
AU  - T. N. Barbolina
TI  - Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements
JO  - Diskretnaya Matematika
PY  - 2007
SP  - 95
EP  - 104
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2007_19_1_a11/
LA  - ru
ID  - DM_2007_19_1_a11
ER  - 
%0 Journal Article
%A O. A. Emets
%A T. N. Barbolina
%T Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements
%J Diskretnaya Matematika
%D 2007
%P 95-104
%V 19
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2007_19_1_a11/
%G ru
%F DM_2007_19_1_a11

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider an application of regular partitions of a space to the solution of Euclidean combinatorial optimisation problems, in particular, conditional optimisation problems on arrangements. We introduce the notion of points of the space equivalent with respect to arrangements and show that the introduced relation between points is an equivalence relation. We give algorithms to search for an element of the set of arrangements which is a representative of the combinatorial class closest to a given class with respect to the lexicographic order (increasing or decreasing). We consider also a new class of optimisation problems, namely, problems of linear conditional lexicographic maximisation on arrangements. We suggest and analyse algorithms for solving the problems of this class. The algorithms are based on the ordered checking of admissible points in the lexicographic (increasing or decreasing) order and use the algorithms to search for the closest element of the set of arrangements mentioned above.

[1] Stoyan Yu. G., Єmets O. O., Teoriya i metodi evklidovoïkombinatornoïoptimizatsiï, Institut sistemnikh doslidzhen osviti, Kiïv, 1993 | Zbl

[2] Sergienko I. V., Kaspshitskaya M. F., Modeli i metody resheniya na EVM kombinatornykh zadach optimizatsii, Naukova Dumka, Kiev, 1981 | MR

[3] Emets O. A., Nedobachii S. I., Kolechkina L. N., “Neprivodimaya sistema ogranichenii kombinatornogo mnogogrannika v drobno-lineinoi zadache optimizatsii na perestanovkakh”, Diskretnaya matematika, 13:1 (2001), 110–118 | MR | Zbl

[4] Valuiskaya O. A., Emets O. A., Romanova N. G., “Vypukloe prodolzhenie mnogochlenov, zadannykh na poliperestanovkakh, modifitsirovannym metodom Stoyana–Yakovleva”, Zh. vych. matem. i matem. fiz., 42:4 (2002), 591–596 | MR | Zbl

[5] Stoyan Yu. G., Yakovlev S. V., Emets O. A., Valuiskaya O. A., “Postroenie vypuklykh prodolzhenii dlya funktsii, zadannykh na gipersfere”, Kibernetika i sistemnyi analiz, 1998, no. 2, 1–11

[6] Єmets O. O., Roskladka A. A., “Pro otsinki minimumiv tsilovikh funktsii pri optimizatsiïna spoluchennyakh”, Ukr. matem. zh., 51:8 (1999), 1118–1121 | MR

[7] Єmets O. O., Kolєchkina L. M., “Zadachi optimizatsiïna perestavlennyakh z drobovo-liniinoyu tsilovoyu funktsiєyu: vlastivosti mnozhini dopustimikh rozv'yazkiv”, Ukr. matem. zh., 52:12 (2000), 1630–1640 | MR

[8] Kolokolov A. A., “Primenenie regulyarnykh razbienii v tselochislennom programmirovanii”, Izv. vuzov. Matematika, 1993, no. 12, 11–30 | MR | Zbl

[9] Kolokolov A. A., Levanova T. V., “Algoritmy dekompozitsii i perebora $L$-klassov dlya resheniya nekotorykh zadach razmescheniya”, Vestnik Omskogo univ., 1996, no. 1, 21–23 | Zbl

[10] Korbut A. A., Finkelshtein Yu. Yu., Diskretnoe programmirovanie, Nauka, Moskva, 1969 | MR | Zbl