Optimal Weighted Ancestry Relationships
TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES
Pagination or Media Count:
An efficient solution method is given for a class of practical optimization problems requiring the determination of a consistent partial ordering for sets of objects, events, preferences, etc. These problems are characterized by the existence of noisy or contradictory links of varying strengths. The origin of this class of problems is an anthropological study in which it is desired to specify a global chronological ordering of ancient cemetery data. A mathematical formulation is given which subsumes this and a variety of related problems within the framework of selecting a maximally consonant set of arcs in a weighted network. The authors show that the problem can be solved by an elegant one-pass algorithm.
- Operations Research