Exact balancing is not always good
type: Item
instance of: scholarly article
title: Exact balancing is not always good
zbMATH Open document ID: 0587.68033
DOI: 10.1016/0020-0190(86)90148-1
author: Marc Snir
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: The following recurrence relation frequently occurs in the analysis of divide-and-conquer algorithms: \[ M_ f(0)=0,\quad M_ f(n+1)=f(n+1)+\min_{i+j=n}(M_ f(i)+M_ f(j)). \] In these applications, f is the cost of merging two subproblems, wereas \(M_ f(i)\) and \(M_ f(j)\) are the costs of solving each subproblem; f is monotonic nondecreasing. In this paper we consider such recurrences, when f is not assumed to be convex.
Mathematics Subject Classification ID: 68W99
Mathematics Subject Classification ID: 65Q05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3943018
zbMATH Keywords: balanced trees
zbMATH Keywords: optimization problem on binary trees
zbMATH Keywords: analysis of divide- and-conquer algorithms
zbMATH Keywords: merging
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90148-1
OpenAlex ID: W2079755555
cites work: Q4773298
cites work: Divide and conquer for linear expected time
cites work: Recurrence relations based on minimization
Recommended article: A case where balancing is harmful
Recommended article: Almost balancing numbers
Recommended article: Balancing a sample almost perfectly
Recommended article: Balanced approximation can be optimal
description: scientific article; zbMATH DE number 3943018