Geodesic
Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements
Diskretnaya Matematika, Tome 19 (2007) no. 1, pp. 95-104

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. 
@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},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2007},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2007_19_1_a11/
%G ru
%F DM_2007_19_1_a11
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/