#### DOCUMENTA MATHEMATICA,
Vol. Extra Volume: Optimization Stories (2012), 199-210

** Thomas L. Gertzen and Martin Grötschel **
Flinders Petrie, the Travelling Salesman Problem,
and the Beginning of Mathematical Modeling
in Archaeology

This article describes one of the first attempts to use mathematical modeling
and optimization in archaeology. William Matthew Flinders Petrie (1853--1942),
eminent British archaeologist, excavating a large graveyard at Naqada in
Upper Egypt suggested in his article «Sequences in Prehistoric Remains»
[17] to employ a «distance function» to describe the «closeness of graves
in time». Petrie's grave distance is known today as Hamming metric, based
on which he proposed to establish the chronology of the graves, i.e., the
correct sequence of points in time when the graves were built (briefly
called seriation). He achieved this by solving a graph theoretic problem
which is called weighted Hamiltonian path problem today and is, of course,
equivalent to the symmetric travelling salesman problem. This paper briefly
sketches a few aspects of Petrie's biographical background and evaluates
the significance of seriation.

2010 Mathematics Subject Classification: 01A55, 05-03, 90-03, 90C27

Keywords and Phrases: Travelling salesman problem, seriation, Hamming metric, archaeology

Full text: dvi.gz 20 k,
dvi 49 k,
ps.gz 15755 k,
pdf 1549 k.

Home Page of
DOCUMENTA MATHEMATICA