Minimum value in each row of an implicitly-defined totally monotone matrix: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
Line 6: | Line 6: | ||
== Parameters == | == Parameters == | ||
n | $m,n$: dimensions of matrix; assume $m≥n$ | ||
possibly uses a function f to define entries; assume evaluation of f takes time O(1) | possibly uses a function $f$ to define entries; assume evaluation of $f$ takes time $O(1)$ | ||
== Table of Algorithms == | == Table of Algorithms == | ||
Line 18: | Line 18: | ||
|- | |- | ||
| [[Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Naive algorithm]] || 1940 || $O( | | [[Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Naive algorithm]] || 1940 || $O(mn)$ || $O({1})$ || Exact || Deterministic || | ||
|- | |- | ||
| [[SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|SMAWK algorithm]] || 1987 || $O(n({1}+log(n/m)$)) || $O(n)$ | | [[SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|SMAWK algorithm]] || 1987 || $O(n({1}+\log(n/m)$)) || $O(n)$? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01840359 Time] | ||
|- | |- | ||
| [[Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Divide and Conquer]] || 1987 || $O(m*log(n)$) || $O(log(n)$) auxiliary? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01840359 Time] | | [[Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Divide and Conquer]] || 1987 || $O(m*log(n)$) || $O(log(n)$) auxiliary? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01840359 Time] |
Revision as of 08:52, 10 April 2023
Description
Given a totally monotone matrix $A$ whose entries $A(i, j)$ are implicitly defined by some function $f(i, j)$ (assume $f$ takes constant time to evaluate for all relevant $(i, j)$), determine the minimum value in each row.
Parameters
$m,n$: dimensions of matrix; assume $m≥n$
possibly uses a function $f$ to define entries; assume evaluation of $f$ takes time $O(1)$
Table of Algorithms
Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|
Naive algorithm | 1940 | $O(mn)$ | $O({1})$ | Exact | Deterministic | |
SMAWK algorithm | 1987 | $O(n({1}+\log(n/m)$)) | $O(n)$? | Exact | Deterministic | Time |
Divide and Conquer | 1987 | $O(m*log(n)$) | $O(log(n)$) auxiliary? | Exact | Deterministic | Time |