Optimal Weighted Ancestry Relationships

A 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, and the like. 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 results in a minimum weight feedback model. A heuristic is developed similar to the Greedy algorithm for minimum weight spanning trees which requires only one pass through the network.