The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
DOI10.1145/1644015.1644032zbMATH Open1298.68073OpenAlexW2622763161MaRDI QIDQ2930293FDOQ2930293
Authors: Lawrence L. Larmore, Yan Zhang, Wolfgang W. Bein, Mordecai J. Golin 
Publication date: 18 November 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.1278
Recommendations
- Monotonicity of quadratic-approximation algorithms
- Extending the quadrangle inequality to speed-up dynamic programming
- A method for obtaining efficient lower bounds for monotone complexity
- Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids
- The monotone circuit complexity of quadratic Boolean functions
- A quadratic speedup theorem for iterative arrays
- Algorithms and Computation
- A solution to fourth Qi's conjecture on a complete monotonicity
- Monotonic iterative algorithms for a quasicomplementarity problem
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
Online algorithms; streaming algorithms (68W27) Programming involving graphs or networks (90C35) Data structures (68P05) Searching and sorting (68P10)
Cited In (10)
- Speeding up dynamic programming in the line-constrained \(k\)-median
- On an efficient dynamic programming technique of F. F. Yao
- Speeding up dynamic programming in the line-constrained \(k\)-median
- Extending the quadrangle inequality to speed-up dynamic programming
- Online Dynamic Programming Speedups
- A tight threshold bound for search trees with 2-way comparisons
- Scheduling with gaps: new models and algorithms
- Optimal competitiveness for the rectilinear Steiner arborescence problem
- Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks
- Online dynamic programming speedups
This page was built for publication: The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930293)
