|
Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements
O. A. Emets, T. N. Barbolina
Abstract:
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.
Received: 03.04.2003
Citation:
O. A. Emets, T. N. Barbolina, “Classes of lexicographic equivalence in Euclidean combinatorial optimisation on arrangements”, Diskr. Mat., 19:1 (2007), 95–104; Discrete Math. Appl., 17:1 (2007), 77–86
Linking options:
https://www.mathnet.ru/eng/dm12https://doi.org/10.4213/dm12 https://www.mathnet.ru/eng/dm/v19/i1/p95
|
|