Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T00:59:54.170Z Has data issue: false hasContentIssue false
  • English
  • Français

Extrema of a Class of Functions on a Finite Set

Published online by Cambridge University Press:  20 November 2018

Kenneth W. Lebensold
Kenneth W. Lebensold*
Affiliation:
City College of New York, New York, New York
Rights & Permissions [Opens in a new window]

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
Canadian Journal of Mathematics , Volume 26 , Issue 4 , August 1974 , pp. 806 - 819
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
3. Supnick, Fred, Extreme Hamiltonian lines, Ann. of Math. 66 (1957), 181.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