Cache-oblivious dynamic programming

Rezaul Alam Chowdhury; Vijaya Ramachandran

doi:10.1145/1109557.1109622

Cache-oblivious dynamic programming

Rezaul Alam Chowdhury
, Vijaya Ramachandran

Computer Science

Stony Brook University

University of Texas at Austin

Research output: Contribution to conference › Paper › peer-review

57 Scopus citations

Abstract

We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.

Original language	English
Pages	591-600
Number of pages	10
DOIs	https://doi.org/10.1145/1109557.1109622
State	Published - 2006
Event	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006

Conference

Conference	Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	Miami, FL
Period	01/22/06 → 01/24/06

Access to Document

10.1145/1109557.1109622

Cite this

@conference{372f339272654e2a8a5b61957aadc614,

title = "Cache-oblivious dynamic programming",

abstract = "We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.",

author = "Chowdhury, \{Rezaul Alam\} and Vijaya Ramachandran",

year = "2006",

doi = "10.1145/1109557.1109622",

language = "English",

pages = "591--600",

note = "Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 22-01-2006 Through 24-01-2006",

}

TY - CONF

T1 - Cache-oblivious dynamic programming

AU - Chowdhury, Rezaul Alam

AU - Ramachandran, Vijaya

PY - 2006

Y1 - 2006

N2 - We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.

AB - We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.

UR - https://www.scopus.com/pages/publications/33244497406

U2 - 10.1145/1109557.1109622

DO - 10.1145/1109557.1109622

M3 - Paper

SP - 591

EP - 600

T2 - Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 22 January 2006 through 24 January 2006

ER -

Cache-oblivious dynamic programming

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this