Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences

摘要

In this paper, upper bounds are presented for the solution of the following multidimensional divide-and-conquer maximin recurrence [GRAPHICS] where p greater than or equal to 2, 1 less than or equal to k, f is an arbitrary nondecreasing function, and "smin(1 less than or equal to i less than or equal to p)((k)) f(n(i))" denotes "the sum of the smallest k numbers among f(n(1)), f(n(2)),..., and f(n(p))". All the presented upper bounds are at most [log(2)k] + p times the exact solution of G(n). The derivation of the upper bounds is based on properties of partition trees. For k = 1 and k = p - 1 we obtain, respectively, two of the recurrences previously studied by Alonso et al. (SIAM J. Discrete Math. 8 (1995) 428-447). In both of these two cases, our results improve theirs. (C) 2000 Published by Elsevier Science B.V. All rights reserved. [References: 15]