History

Please fill in your query. A complete syntax description you will find on the General Help page.
On the planar piecewise quadratic 1-center problem. (English)
Algorithmica 57, No. 2, 252-283 (2010).
Summary: In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We assume that the transportation costs of the demand points to the serving facility are convex functions $\{Q _{i }\}$, $i=1,\dots ,n$, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions of the coordinates of the facility location. In the continuous case, using results on LP-type models by {\it K. L. Clarkson} [J. Assoc. Comput. Mach. 42, No.~2, 488‒499 (1995; Zbl 0885.65063)], {\it J. Matoušek, M. Sharir} and {\it E. Welzl} [Algorithmica 16, No.~4‒5, 498‒516 (1996; Zbl 0857.68119)], and the derandomization technique in [{\it B. Chazelle} and {\it J. Matoušek}, J. Algorithms 21, No.~3, 579‒597 (1996; Zbl 0864.68040)], we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can get a direct $O(n \log n)$ deterministic algorithm, based on [{\it M. E. Dyer}, “A class of convex programs with applications to computational geometry", in: Proceedings of the 8th ACM symposium on computational geometry, 9‒15 (1992)], to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of {\it N. Megiddo} [J. Assoc. Comput. Mach. 30, 852‒865 (1983; Zbl 0627.68034)], and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity.