NDLI: The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity

Content Provider	ACM Digital Library
Author	Bein, Wolfgang Golin, Mordecai J. Zhang, Yan Larmore, Lawrence L.
Copyright Year	2009
Abstract	There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of totally monotone matrices. Although both of these techniques use a quadrangle inequality and seem similar, they are actually quite different and have been used differently in the literature. In this article we show that the Knuth-Yao technique is actually a direct consequence of total monotonicity. As well as providing new derivations of the Knuth-Yao result, this also permits to solve the Knuth-Yao problem directly using the SMAWK algorithm. Another consequence of this approach is a method for solving $\textit{online}$ versions of problems with the Knuth-Yao property. The online algorithms given here are asymptotically as fast as the best previously known static ones. For example, the Knuth-Yao technique speeds up the standard dynamic program for finding the optimal binary search tree of $\textit{n}$ elements from $Θ(n^{3})$ down to $O(n^{2}),$ and the results in this article allow construction of an optimal binary search tree in an online fashion (adding a node to the left or the right of the current nodes at each step) in $\textit{O}(\textit{n})$ time per step.
Starting Page	1
Ending Page	22
Page Count	22
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1644015.1644032
Volume Number	6
Issue Number	1
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-12-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dynamic programming Binary search tree Online computation Totally monotone
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity ∗

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity

The knuth-yao quadrangle-inequality speedup is a consequence of total-monotonicity.

The knuth-yao quadrangle-inequality speedup is a consequence of total-monotonicity ∗.

The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity

Online maintenance of k-medians and k-covers on a line.

Online maintenance of k-medians and k-covers on a line (2004).

Online Maintenance of k-Medians and k-Covers on a Line (2004)

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity

Similar Documents

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity ∗

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity

The Knuth-Yao Quadrangle-Inequality Speedup is a Consequence of Total-Monotonicity

The knuth-yao quadrangle-inequality speedup is a consequence of total-monotonicity.

The knuth-yao quadrangle-inequality speedup is a consequence of total-monotonicity ∗.

The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity

Online maintenance of k-medians and k-covers on a line.

Online maintenance of k-medians and k-covers on a line (2004).

Online Maintenance of k-Medians and k-Covers on a Line (2004)

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity