×

Aggregation of binary relations: algorithmic and polyhedral investigations. (English) Zbl 0606.68036

Naturwissenschaftliche Fakultät der Universität Augsburg. 191 p. (1986).
We are concerned here with problems of binary relations which are of the following type: Given a family of m binary relations \(R_ 1,R_ 2,...,R_ m\) on a set N, find a binary relation \(R^*\) of N of a pre- defined type, which simultaneously approximates all relations of the family. The approximation is to be best according to a given distance measure.
These are the so-called problems of aggregation of binary relations. They arise in qualitative data analysis, in social choice theory, in paired comparisons methods, etc.
In this dissertation we investigate a class of such problems where the distance function to be minimized by \(R^*\), is \[ {\mathcal F}(R;R_ 1,...,R_ m):=\sum^{m}_{k=1}| R\Delta R_ k|. \] This measure has been used widely and is considered appropriate for many applications.
In the first part of this dissertation we analyse the computational complexity status all of the aggregation problems which arise when \(R^*\) is required to satisfy one or more of the following properties: reflexivity, symmetry, antisymmetry, transitivity, restricted transitivity and completeness. Some combinations of these properties obviously result in trivial problems. We prove that all other problems are \({\mathcal N}{\mathcal P}\)-hard. In some cases we prove that they are already \({\mathcal N}{\mathcal P}\)-hard when the number of binary relations is fixed.
The second part of this thesis is devoted to the study of the aggregation problem where \(R^*\) is required to be an equivalence relation, i.e., a reflexive, symmetric and transitive relation. This problem is \({\mathcal N}{\mathcal P}\)-hard, and has been intensively investigated due to its wide range of applicability.
We study this problem from a polyhedral point-of-view. We define and investigate a polytope whose vertices are in one-to-one correspondence with the feasible solutions of the problem. We obtain a partial characterization of this polytope and use this to design a linear programming based cutting plane algorithm to solve the problem. We describe in detail the algorithm we have implemented and report on the computational results obtained. Other methods which have been proposed for this problem are also discussed.

MSC:

68Q25 Analysis of algorithms and problem complexity
03E20 Other classical set theory (including functions, relations, and set algebra)
90C05 Linear programming