In this paper, we are concerned with the following problem: Let S be a finite set and Sm * ⊂ 2S a collection of subsets of S each of whose members has m elements (m a positive integer). Let f be a real-valued function on S and, for p ∊ Sm *, define f(P) as Σs∊p f (s). We seek the minimum (or maximum) of the function f on the set Sm *.The Traveling Salesman Problem is to find the cheapest polygonal path through a given set of vertices, given the cost of getting from any vertex to any other. It is easily seen that the Traveling Salesman Problem is a special case of this system, where S is the set of all edges joining pairs of points in the vertex set, Sm * is the set of polygons, each polygon has m elements (m = no. of points in the vertex set = no. of edges per polygon), and f is the cost function.
Lebensold, Kenneth W. Extrema of a Class of Functions on a Finite Set. Canadian journal of mathematics, Tome 26 (1974) no. 4, pp. 806-819. doi: 10.4153/CJM-1974-076-x
@article{10_4153_CJM_1974_076_x,
author = {Lebensold, Kenneth W.},
title = {Extrema of a {Class} of {Functions} on a {Finite} {Set}},
journal = {Canadian journal of mathematics},
pages = {806--819},
year = {1974},
volume = {26},
number = {4},
doi = {10.4153/CJM-1974-076-x},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1974-076-x/}
}
TY - JOUR
AU - Lebensold, Kenneth W.
TI - Extrema of a Class of Functions on a Finite Set
JO - Canadian journal of mathematics
PY - 1974
SP - 806
EP - 819
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1974-076-x/
DO - 10.4153/CJM-1974-076-x
ID - 10_4153_CJM_1974_076_x
ER -
%0 Journal Article
%A Lebensold, Kenneth W.
%T Extrema of a Class of Functions on a Finite Set
%J Canadian journal of mathematics
%D 1974
%P 806-819
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1974-076-x/
%R 10.4153/CJM-1974-076-x
%F 10_4153_CJM_1974_076_x
[1] 1.
Farkas, J., Uber die Théorie der einfachen Ungleichungen, J. Reine Angew. Math.124 (1902), 1–27. Google Scholar
[2] 2.
Savage, S. L., Weiner, P., and Krone, M. J., Convergent local search, Research Report No. 14, Yale University, Department of Computer Sciences, March 1973. Google Scholar
[3] 3.
Supnick, Fred, Extreme Hamiltonian lines, Ann. of Math.66 (1957), 181. Google Scholar
[4] 4.
Weiner, P., Savage, S. L., and Bagchi, A., Neighborhood search algorithms for finding optimal traveling salesman tours must be inefficient, Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, April, 1973. Google Scholar
