๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Biing-Feng Wang

Book ID
104326640
Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
250 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper, upper bounds are presented for the solution of the following multidimensional divide-and-conquer maximin recurrence

where pยฟ2; 16kยกp; f is an arbitrary nondecreasing function, and "smin (k) 16i6p f(ni)" denotes "the sum of the smallest k numbers among f(n1); f(n2); : : : ; and f(np)". 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.

๐Ÿ“œ SIMILAR VOLUMES

Tighter Bounds on the Solution of a Divi
Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
โœ Biing-Feng Wang ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 207 KB

Let M n be defined by the recurrence where f is an arbitrary nondecreasing function and M 1 is given. The recurrence ลฝ . M n is a divide-and-conquer maximin recurrence, which occurs in a variety of ลฝ . problems in the analysis of algorithms. In this paper, a new upper bound on M n is first derived.