Tytuł pozycji:
Determining an estimate of an equivalence relation for moderate and large sized sets
This paper presents two approaches to determining estimates of an equivalence relation on the
basis of pairwise comparisons with random errors. Obtaining such an estimate requires the solution of
a discrete programming problem which minimizes the sum of the differences between the form of the
relation and the comparisons. The problem is NP hard and can be solved with the use of exact algorithms
for sets of moderate size, i.e. about 50 elements. In the case of larger sets, i.e. at least 200 comparisons
for each element, it is necessary to apply heuristic algorithms. The paper presents results (a statistical
preprocessing), which enable us to determine the optimal or a near-optimal solution with
acceptable computational cost. They include: the development of a statistical procedure producing comparisons
with low probabilities of errors and a heuristic algorithm based on such comparisons. The
proposed approach guarantees the applicability of such estimators for any size of set.