This is a revision of the author’s 1982 doctoral thesis on facility location algorithms and their computational complexity. After Chapter 0 which is an introduction, four chapters are concerned with discrete facility location (i.e., on a given graph). Chapter 1 discusses p-center problems and round-trip p-center problems when the graph is a tree. Corresponding covering problems are formulated and polynomial time algorithms are presented to solve them. Chapter 2 treats center problems with unequal setup costs including the simple plant location problem. Chapters 3 and 4 are devoted to p-median and p-center problems where mutual communications between facilities (or between a client and several new facilities) are present. Again, polynomial time algorithms are given when the graph is a tree, while the problems come out to be NP-hard when it is not a tree. In Chapter 5, continuous facility location (i.e., in the plane) is investigated where the distance is rectilinear. Based on an extension of Farkas’ Lemma, an algorithm is given to find all efficient points in the plane. Finally, Chapter 6 collects results on totally balanced matrices (which are shown to be the matrices transformable into standard greedy form) and on chordal graphs.
The monograph appears to be a considerable contribution to the theory of facility location algorithms. Some of the results (and related ones) have been reviewed in more detail by B. C. Tansel, R. L. Francis and T. J. Lowe [Manage. Sci. 29, 482-511 (1983; Zbl 0513.90022 and Zbl 0513.90023)] and P. M. Dearing [Oper. Res. Lett. 4, 95-98 (1985; Zbl 0572.90022)].