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<p, f is an ar bitrary nondecreasing function, and "smin(1 less than or equal to i less th an 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 ar e 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 studie d by Alonso et al. (SIAM J. Discrete Math. 8 (1995) 428-447). In both of th ese two cases, our results improve theirs. (C) 2000 Published by Elsevier S cience B.V. All rights reserved.