Recurrence relations based on minimization and maximization
type: Item
instance of: scholarly article
title: Recurrence relations based on minimization and maximization
zbMATH Open document ID: 0597.65060
DOI: 10.1016/0022-247X(85)90170-2
published in: Journal of Mathematical Analysis and Applications
publication date: 1985-01-01T00:00:00Z
review text: From the article: Explicit and asymptotic solutions are presented to the recurrence \(M(1)=g(1)\), \[ M(n+1)=g(n+1)+\min_{1\leq t\leq n}(\alpha M(t)+\beta M(n+1-t)) \] for the cases (1) \(\alpha +\beta <1\), \(\log_ 2\alpha /\log_ 2\beta\) is rational, and \(g(n)=\delta_{n1}\). (2) \(\alpha +\beta >1\), \(\min (\alpha,\beta)>1\), \(\log_ 2\alpha /\log_ 2\beta\) is rational, and (a) \(g(n)=\delta_{n1}\), (b) \(g(n)=1\). Such recurrences arise commonly in the analysis of algorithms, especially algorithms based on dynamic programming or divide and conquer techniques.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 65Q05
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 3963116
zbMATH Keywords: recurrences
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: dynamic programming
zbMATH Keywords: divide and conquer techniques
author: Sanjiv Kapoor
author: Edward M. Reingold
MaRDI profile type: Publication
cites work: Recurrence relations based on minimization
cites work: Q3935355
cites work: Q4057549
cites work: On a Greedy Heuristic for Complete Matching
cites work: Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
description: scientific article; zbMATH DE number 3963116