|
-
Ключові слова:
математика, mathematics, mathematique, matematyka, matematica, mathematica ; оптимізація, оптимизация, optimization
-
Анотація:
In this paper we present an original algorithm and data structures to solve the Bichromatic Closest Pair problem in metrics L1. We got O(n) time for the case of sets, each of which is coincided with the set of its maximums regarding to dominance, and O(nlogn) time in general. In addition, we o?er a modi?cation randomized Khuller and Matthias algorithm [3], which improves performance. So, Khuller and Matias algorithm approximates minimal distance with the closeness of multiplicative constant, that is ifd - minimal distance, and d¤ - approximation, then d¤< d<ad¤, where a > 1. In standard situation, a = 4, but this result can be perfected to 1+e, for any e > 0, keeping the linear time algorithm.
-
Є складовою частиною документа:
-
Теми документа
-
Окремі фонди та колекції КНУ // праці авторів КНУТШ, труды авторов КНУТШ, работы авторов КНУТШ
|
