On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
Author:
- 1 August 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (3) , 725-738
Abstract
The paper is divided into two main sections. The first deals with a multidimensional search technique of Megiddo [J. Assoc. Comput. Mach., 31 (1984), pp. 114–127], and suggests an improvement. The second gives an application of the technique to the Euclidean one-centre problem in $\mathbb{R}^d $. An algorithm of time-complexity $O(3^{(d + 2)^2 } n)$ is derived for this problem. This improves the best previous bound even in the case $d = 2$.
Keywords
This publication has 11 references indexed in Scilit:
- Linear Time Algorithms for Two- and Three-Variable Linear ProgramsSIAM Journal on Computing, 1984
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- The Weighted Euclidean 1-Center ProblemMathematics of Operations Research, 1983
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983
- Efficient Algorithms for the (Weighted) Minimum Circle ProblemOperations Research, 1982
- The weighted euclidean 1-center problemOperations Research Letters, 1982
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- Single Facility $l_p $-Distance Minimax LocationSIAM Journal on Algebraic Discrete Methods, 1980
- On the complexity of computations under varying sets of primitivesLecture Notes in Computer Science, 1975
- Time bounds for selectionJournal of Computer and System Sciences, 1973