The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity
From MaRDI portal
Publication:2930293
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
Cited in
(10)- Scheduling with gaps: new models and algorithms
- Online dynamic programming speedups
- On an efficient dynamic programming technique of F. F. Yao
- Online Dynamic Programming Speedups
- Extending the quadrangle inequality to speed-up dynamic programming
- Speeding up dynamic programming in the line-constrained \(k\)-median
- A tight threshold bound for search trees with 2-way comparisons
- Speeding up dynamic programming in the line-constrained \(k\)-median
- Optimal competitiveness for the rectilinear Steiner arborescence problem
- Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks
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)
