Recurrence relations based on minimization and maximization

DOI10.1016/0022-247X(85)90170-2MaRDI QIDQ1079343zbMATH OpenFDO

Authors Sanjiv Kapoor, Edward M. Reingold

Publication date 1985

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-247X(85)90170-2

zbMATH Keywords

analysis of algorithmsdivide and conquer techniquesdynamic programmingrecurrences

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Discrete mathematics in relation to computer science (68R99) Dynamic programming (90C39)

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.

Recommendations

• An asymptotic theory for recurrence relations based on minimization and maximization.
• Solution of a Divide-and-Conquer Maximin Recurrence
• Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
• Exact balancing is not always good
• Multidimensional Divide-and-Conquer Maximin Recurrences

Cites work

• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• On a Greedy Heuristic for Complete Matching
• Recurrence relations based on minimization

Cited in

(12)

• An asymptotic theory for recurrence relations based on minimization and maximization.
• Solutions of two minmax recurrences in parallel processing with variable recombination overhead
• On the cost of optimal alphabetic code trees with unequal letter costs
• Asymptotic limits of a new type of maximization recurrence with an application to bioinformatics
• scientific article; zbMATH DE number 6378818 (Why is no real title available?)
• Exact solution of a minimal recurrence
• Analytic solution of a special class of recurrence relations for the analysis of recursive algorithms
• scientific article; zbMATH DE number 3846336 (Why is no real title available?)
• Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
• scientific article; zbMATH DE number 2172765 (Why is no real title available?)
• Analysis of a Recurrence Arising from a Construction for Nonblocking Networks
• An Algorithm for Computing Minimal Bidirectional Linear Recurrence Relations

This page was built for publication: Recurrence relations based on minimization and maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079343)