Geodesic
Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
Documenta mathematica, Optimization Stories (2012), pp. 199-210.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 01A55, 05-03, 90-03, 90C27
Keywords: travelling salesman problem, seriation, Hamming metric, archaeology 
@article{DOCMA_2012__S3__a22,
     author = {Gertzen, Thomas L. and Gr\"otschel, Martin},
     title = {Flinders {Petrie,} the travelling salesman problem, and the beginning of mathematical modeling in archaeology},
     journal = {Documenta mathematica},
     pages = {199--210},
     publisher = {mathdoc},
     volume = {Optimization Stories},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a22/}
}
TY  - JOUR
AU  - Gertzen, Thomas L.
AU  - Grötschel, Martin
TI  - Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
JO  - Documenta mathematica
PY  - 2012
SP  - 199
EP  - 210
VL  - Optimization Stories
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a22/
LA  - en
ID  - DOCMA_2012__S3__a22
ER  - 
%0 Journal Article
%A Gertzen, Thomas L.
%A Grötschel, Martin
%T Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
%J Documenta mathematica
%D 2012
%P 199-210
%V Optimization Stories
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a22/
%G en
%F DOCMA_2012__S3__a22
Gertzen, Thomas L.; Grötschel, Martin. Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology. Documenta mathematica, Optimization Stories (2012), pp. 199-210. http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a22/