Optimal Weighted Ancestry Relationships

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1972
Accession Number
AD0752754

Entities

People

  • D. Klingman
  • Fred W. Glover
  • T. Klastorin

Organizations

  • University of Texas at Austin

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Buildings And Structures
  • Cemeteries
  • Classification
  • Commerce
  • Coverings
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Military Research
  • Numbers
  • Optimization
  • Real Numbers
  • Security
  • United States
  • Universities

Readers

  • Archaeological Resource Survey
  • Operations Research
  • Theoretical Analysis.