No CrossRef data available.
Article contents
Extrema of a Class of Functions on a Finite Set
Published online by Cambridge University Press: 20 November 2018
Extract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
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∊pf (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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Canadian Mathematical Society 1974
References
1.
Farkas, J., Uber die Théorie der einfachen Ungleichungen, J. Reine Angew. Math.
124 (1902), 1–27.Google Scholar
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
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
You have
Access