Determining an estimate of an equivalence relation for moderate and large sized sets

Leszek Klukowski ()

Operations Research and Decisions, 2017, vol. 27, issue 2, 45-58

Abstract: 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.

Keywords: estimation of an equivalence relation; pairwise comparisons with random errors; concept of nearest adjoining order (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ord.pwr.edu.pl/assets/papers_archive/1286%20-%20published.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wut:journl:v:2:y:2017:p:45-58:id:1286

DOI: 10.5277/ord170203

Access Statistics for this article

More articles in Operations Research and Decisions from Wroclaw University of Science and Technology, Faculty of Management Contact information at EDIRC.
Bibliographic data for series maintained by Adam Kasperski ().