Accession Number:

AD0752754

Title:

Optimal Weighted Ancestry Relationships

Descriptive Note:

Research Rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Report Date:

1972-09-01

Pagination or Media Count:

18.0

Abstract:

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE