New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 500 | older 500) (20 | 50 | 100 | 250 | 500)
- 12:15, 15 February 2023 LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of $O(n)$-sized vectors per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1948 == Reference == -")
- 12:15, 15 February 2023 Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu_i*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1921 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19210010104")
- 12:15, 15 February 2023 Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) (hist | edit) [464 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary words (Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/360767.360802")
- 12:15, 15 February 2023 Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/129902.129906")
- 12:15, 15 February 2023 Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf")
- 12:15, 15 February 2023 Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == http://davis.wpi.edu/~matt/courses/clipping/")
- 12:15, 15 February 2023 Gupta-Sproull algorithm (Line Drawing Line Drawing) (hist | edit) [459 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf")
- 12:15, 15 February 2023 Xiaolin Wu's line algorithm (Line Drawing Line Drawing) (hist | edit) [423 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1991 == Reference == http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf")
- 12:15, 15 February 2023 Digital Differential Analyzer (Line Drawing Line Drawing) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Bresenham's line algorithm (Line Drawing Line Drawing) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1965 == Reference == https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf")
- 12:15, 15 February 2023 Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613")
- 12:15, 15 February 2023 Naive algorithm (Line Drawing Line Drawing) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [383 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(logn)$^{1.{58}5}) == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://ieeexplore.ieee.org/document/1926/")
- 12:15, 15 February 2023 Radix sorting method (General Permutations Generating Random Permutations) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Need to keep track of randomly generated numbers, but otherwise see radix sort) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1887 == Reference == -")
- 12:15, 15 February 2023 Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2001 == Reference == https://ieeexplore.ieee.org/document/917698")
- 12:15, 15 February 2023 Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n (logn)$^{2}) == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/236869.236882) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236869.236882")
- 12:15, 15 February 2023 Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/document/1162043) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1162043")
- 12:15, 15 February 2023 Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1968 == Reference == https://dl.acm.org/citation.cfm?id=1476610")
- 12:15, 15 February 2023 Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1966 == Reference == http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf")
- 12:15, 15 February 2023 Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1976 == Reference == https://ieeexplore.ieee.org/document/1162805")
- 12:15, 15 February 2023 Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1163036/")
- 12:15, 15 February 2023 Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf")
- 12:15, 15 February 2023 Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log^{3}(E)$ loglogE) == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf")
- 12:15, 15 February 2023 Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (Derived: You only need a constant number of variables that are of $O(1)$ size at any given time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == -")
- 12:15, 15 February 2023 Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1873 == Reference == -")
- 12:15, 15 February 2023 Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{2})$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://collaborate.princeton.edu/en/publications/a-note-on-finding-the-bridges-of-a-graph")
- 12:15, 15 February 2023 Mucha and Sankowski ( Maximum-Weight Matching) (hist | edit) [268 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://dl.acm.org/doi/10.1109/FOCS.2004.40")
- 12:15, 15 February 2023 Edmonds (Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn^{2})$?? words (At worst, keeps track of the entire sequence of graphs created; it's possible this can be improved?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf")
- 12:15, 15 February 2023 Micali; Vazirani ( Maximum-Weight Matching) (hist | edit) [276 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 12:15, 15 February 2023 Lipton; Mehta (2-player Nash Equilibria) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????) == Space Complexity == (see sheet {2}) words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 12:15, 15 February 2023 Lemke–Howson algorithm (2-player Nash Equilibria) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^{($O(n+m)$)} (previously $O(n^{4})$????) == Space Complexity == $O(mn)$? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1")
- 12:15, 15 February 2023 Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [464 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Either graph interpretation maintains O(n^2) orientations and O(n) potential or matrix interpretation manipulates an O(n)*O(n) auxiliary matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1955 == Reference == https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf")
- 12:15, 15 February 2023 De Prisco (Approximate OBST Optimal Binary Search Trees) (hist | edit) [502 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary probability distribution, and three phases that alter a single tree that eventually is the result) == Description == == Approximate? == Approximate Approximation Factor: Upper bound: $H + 1 - p_0 - p_n + p_{max}$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/a...")
- 12:15, 15 February 2023 Levcopoulos; Lingas; Sack (Approximate OBST Optimal Binary Search Trees) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary list of initial size $4n$) == Description == == Approximate? == Approximate Approximation Factor: $1 + \epsilon$ == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0304397589901345")
- 12:15, 15 February 2023 Yao (OBST Optimal Binary Search Trees) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://doi.org/10.1137/0603055) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://doi.org/10.1137/0603055")
- 12:15, 15 February 2023 Naive algorithm (OBST Optimal Binary Search Trees) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^n /n \sqrt{n})$ == Space Complexity == $O({1})$ words (Derived: Constant space to verify optimality. Constant space if you can enumerate the trees in-situ.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
- 12:15, 15 February 2023 Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
- 12:15, 15 February 2023 Hu–Tucker algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/10.1137/0121057) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://epubs.siam.org/doi/10.1137/0121057")
- 12:15, 15 February 2023 Garsia–Wachs algorithm (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/epdf/10.1137/0206045, See implementation of MINTREE) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://epubs.siam.org/doi/abs/10.1137/0206045")
- 12:15, 15 February 2023 Modified Knuth's DP algorithm (OBST Optimal Binary Search Trees) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4492658) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.cs.bgu.ac.il/~michaluz/seminar/Knuth71.pdf")
- 12:15, 15 February 2023 Heap's algorithm (All Permutations All Permutations) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O(n)$ auxiliary words ($O(n)$-sized stack or array necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://academic.oup.com/comjnl/article/6/3/293/360213")
- 12:15, 15 February 2023 SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n({1}+log(n/m)$)) == Space Complexity == $O(n)$ auxiliary? words (Need to keep track of which columns aren't pruned. Also uses $O(n)$ auxiliary space during prune-and-search?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359")
- 12:15, 15 February 2023 Steinhaus–Johnson–Trotter algorithm (All Permutations All Permutations) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O({1})$ auxiliary words (Determining $x_i$ and $y_i$ each iteration can be done in constant space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1963 == Reference == https://www.ams.org/journals/mcom/1963-17-083/S0025-5718-1963-0159764-2/home.html")
- 12:15, 15 February 2023 Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ auxiliary words (Only needs to keep track of current minimum in current row - once done with a row, can send stored minimum to output and recycle space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Tompkins–Paige algorithm (All Permutations All Permutations) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary words (Keeps track of auxiliary counting array) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://mathscinet.ams.org/mathscinet-getitem?mr=0080380")
- 12:15, 15 February 2023 Faugère F4 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [500 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://linkinghub.elsevier.com/retrieve/...")
- 12:15, 15 February 2023 Faugère F5 algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n+D_reg, D_reg)$^{\omega}) where omega is the exponent on matrix multiplication == Space Complexity == $O(C(n+D_{reg}, D_{reg})$^{2})? words (Seems to keep track of a square matrix (for monomials) of size $O(C(n+D_{reg}, D_{reg})^2$)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/780506.780516")
- 12:15, 15 February 2023 Dual subgradients and the drift-plus-penalty method (Stochastic optimization Convex Optimization (Non-linear)) (hist | edit) [324 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(Vmn)$???? words (involves minimizing an expression with up to O(Vmn) terms per iteration?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference ==")
- 12:15, 15 February 2023 Buchberger's algorithm (Gröbner Bases Gröbner Bases) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == d^{({2}^{(n+o({1})})}) == Space Complexity == d^{({2}^{(n+o({1}))})}?? words (Output may contain that many elements. However, this bound seems very crude/loose) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/1088216.1088219")
- 12:15, 15 February 2023 Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [383 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(nmL)$ words (see orginal paper (noting that O(alpha*log(H*alpha)) = O(L))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0041555380900610")
- 12:15, 15 February 2023 Wolfe; Lemaréchal; Kiwiel (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n+L)$?? words (keeps track of current guess x^{(k)}, and computes bundle G^{(k)}, direction d^{(k)}, and scalar t^{(k)}?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://link.springer.com/content/pdf/10.1007/BFb0120703.pdf")
- 12:15, 15 February 2023 Subgradient method (General, Constrained optimization Convex Optimization (Non-linear)) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} )$ == Space Complexity == $O(n+L)$? words (keep track of current guess x^{(k)}, and needs to compute subgradient g^{(k)}) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1981 == Reference == https://www.springer.com/gp/book/9783642821202")
- 12:15, 15 February 2023 Gomory's cutting method (ILP;MILPs Convex Optimization (Non-linear)) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m)$)? (previously $O(n^{3})$) == Space Complexity == $O(nm+m^{2})$ words (See simplex algorithm, but also O(m) variables and constraints are introduced) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1953 == Reference == https://www.cs.uleth.ca/~benkoczi/OR/read/cutting-stock-LP.pdf")
- 12:15, 15 February 2023 Sattolo's algorithm (Cyclic Permutations Generating Random Permutations) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019086900736")
- 12:15, 15 February 2023 Fisher–Yates/Knuth shuffle (General Permutations Generating Random Permutations) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Need to keep track of which elements have been struck out already) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1938 == Reference == https://www.worldcat.org/title/statistical-tables-for-biological-agricultural-and-medical-research/oclc/14222135")
- 12:15, 15 February 2023 Gosper's algorithm ( Cycle Detection) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ log(\lambda + \mu) t_f) == Space Complexity == \Theta(log(\mu + \lambda)) (https://en.wikipedia.org/wiki/Cycle_detection#Gosper's_algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1978 == Reference == https://www.inwap.com/pdp10/hbaker/hakmem/flows.html#item132")
- 12:15, 15 February 2023 Durstenfeld's Algorithm 235 (General Permutations Generating Random Permutations) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Essentially in-situ) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1964 == Reference == https://dl.acm.org/doi/10.1145/364520.364540")
- 12:15, 15 February 2023 Brent's algorithm ( Cycle Detection) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://maths-people.anu.edu.au/~brent/pd/rpb005.pdf")
- 12:15, 15 February 2023 Floyd's tortoise and hare algorithm ( Cycle Detection) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((\lambda + \mu)$ t_f) == Space Complexity == $O({1})$ Pointer algo (Algorithmic Cryptanalysis) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference == http://pds7.egloos.com/pds/200801/07/29/p636-floyd.pdf")
- 12:15, 15 February 2023 Briggs; Henson; McCormick ( SDD Systems Solvers) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{2}5} loglogn)$ == Space Complexity == () == Description == Multigrid == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == http://www.math.ust.hk/~mamu/courses/531/tutorial_with_corrections.pdf")
- 12:15, 15 February 2023 Kelner; Orecchia; Sidford; Zhu (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m log^{2} (n)$ loglogn) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree of the graph that the Laplacian is for) == Description == Low-stretch spanning tree == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/pdf/1301.6628.pdf")
- 12:15, 15 February 2023 Daitch; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5/4} (log^{2} (n)$ loglogn)^{3/4} log({1}/ϵ)) == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Support Theory (Trusses and Stiffness Matrices) == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://arxiv....")
- 12:15, 15 February 2023 Lee; Peng; Spielman (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary sparse Cholesky decomposition which has $O(n)$ non-zero entries) == Description == Recursive algorithm with sparse Cholesky factorization of Laplacian == Approximate? == Approximate Approximation Factor: The sparse Cholesky decomposition is a 2-approximation == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference...")
- 12:15, 15 February 2023 Naive Implementation (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!)$ == Space Complexity == $O(n^{2})$ Word RAM (Derived: The Leibniz formula for the determinant of the Laplacian can be computed with constant space. The adjugate matrix of the Laplacian takes $n^2$ space.) == Description == Explicitly calculating the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:15, 15 February 2023 Koutis; Miller and Peng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(m log n)$ == Space Complexity == $O(n)$ words (Derived: Uses an auxiliary chain of graphs, which can be kept track of with a single spanning tree) == Description == Incremental sparsifier == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/abs/1102.4842")
- 12:15, 15 February 2023 Blelloch; Koutis; Miller; Tangwongsan (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == m + $O(n/log n)$ words (https://www.cs.cmu.edu/afs/cs.cmu.edu/Web/People/jkoutis/papers/SC10-paper.pdf) == Description == Combinatorial multigrid == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5644892")
- 12:15, 15 February 2023 Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log({1}/ϵ)$ ) == Space Complexity == $O(n)$ words (Derived: The preconditioners used have $O(n)$ non-zero entries) == Description == Maximum-weight-basis (MWB) preconditioners == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.343")
- 12:15, 15 February 2023 Bern; Gilbert; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == () == Description == Support Graph Preconditioning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=1117896")
- 12:15, 15 February 2023 Boman; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(mn^{({1}/{2})})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://epubs.siam.org/doi/10.1137/S0895479801390637")
- 12:15, 15 February 2023 Vaidya (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{({3}/{4})$}) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree (size $O(n)$)) == Description == Using maximum-weight spanning trees == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference ==")
- 12:15, 15 February 2023 Peterson's algorithm ( Mutual Exclusion) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ total communication variables? (see original paper ("requires $2n-1$ shared variables of size $n$")) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf")
- 12:15, 15 February 2023 Naimi-Trehel's algorithm ( Mutual Exclusion) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process keeps track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0743731596900416")
- 12:15, 15 February 2023 Chan-Singhal-Liu ( Mutual Exclusion) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process seems to keep track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1990 == Reference == https://ieeexplore.ieee.org/document/113817")
- 12:15, 15 February 2023 Spielman, Teng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [556 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m log^c n)$ == Space Complexity == $O(n)$ words (Derived: Uses spanning trees and sparse Cholesky factorization which both take $O(n)$ space) == Description == Spectral Sparsification == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/doi/pdf/10.1145/1007352.1007372?casa_token=k60CrC_UJp0AA...")
- 12:14, 15 February 2023 Diffie–Hellman key exchange (Key Exchange Key Exchange) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n) where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1055638")
- 12:14, 15 February 2023 Elliptic-curve Diffie-Hellman (ECDH) (Key Exchange Key Exchange) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n^{2})? where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2006 == Reference == https://csrc.nist.gov/publications/detail/sp/800-56a/revised/archive/2007-03-14")
- 12:14, 15 February 2023 Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion) (hist | edit) [246 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == communication variables? () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1963 == Reference == -")
- 12:14, 15 February 2023 Klein (section 5) (Planar Bipartite Graph Perfect Matching Maximum Cardinality Matching) (hist | edit) [532 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{({4}/{3})$} logV) == Space Complexity == $O(V^{({4}/{3})$})? words (Considers and operates on a graph partition (which still takes up $O(E)=O(V)$ space), and computes shortest-path distances within each graph partition, the total of which requires $O(V^{(4/3)})$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == http:...")
- 12:14, 15 February 2023 Gabow; Tarjan (General Graph MCM Maximum Cardinality Matching) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary? words (https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf")
- 12:14, 15 February 2023 Mucha, Sankowski (general) (General Graph MCM Maximum Cardinality Matching) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2.{37}6})$ == Space Complexity == $O(V^{2})$?? words (Algorithm uses/manipulates constant number of matrices and graphs?) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2004 == Reference == https://ieeexplore.ieee.org/document/1366244")
- 12:14, 15 February 2023 Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [443 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{10/7}*polylog(V)$) == Space Complexity == $O(E + V)$ words (Derived: Uses an augmented graph (copy of the original graph plus an additional node with edges between it and all other nodes)) == Description == Based on electric flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/abs/1307.2205")
- 12:14, 15 February 2023 Blum (General Graph MCM Maximum Cardinality Matching) (hist | edit) [436 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary?? words (Each phase, creates a separate directed graph and solves a reachability problem on it. Can reuse space across phases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf")
- 12:14, 15 February 2023 Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) == Space Complexity == $O(E)$ auxiliary?? words (Designs a flow network and runs pseudoflow algorithms on graph; space can be reused if too many residual graphs are created) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1105.1569")
- 12:14, 15 February 2023 Hash join ( Joins) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n+m)$? words (Need a hash table of at least that size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 12:14, 15 February 2023 Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [550 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication == Space Complexity == $O(VlogV)$??? words (Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2006 == Re...")
- 12:14, 15 February 2023 Sort merge join ( Joins) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn + mlogm)$ == Space Complexity == $O(n+m)$? words (Need sorted lists of indices of input tables) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 12:14, 15 February 2023 Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [456 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(E)$ auxiliary words (creating new graph and using it as input to the Ford-Fulkerson algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764")
- 12:14, 15 February 2023 Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(V)$ auxiliary words (maximal set of vertex-disjoint shortest augmenting paths uses O(V) space to store, taking symmetric difference also uses O(V) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://epubs.siam.org/doi/10.1137/0202019")
- 12:14, 15 February 2023 Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2231712")
- 12:14, 15 February 2023 Nested loop join ( Joins) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ words (Just need to keep track of which rows are being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 12:14, 15 February 2023 Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9254694")
- 12:14, 15 February 2023 Apostolico–Giancarlo Algorithm (Single String Search String Search) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m + s)$ + $O(n)$ == Space Complexity == $O(m)$ words (https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1) == Description == Variant of BM == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1")
- 12:14, 15 February 2023 Raita Algorithm (Single String Search String Search) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Slight variation of BMH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.cin.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf")
- 12:14, 15 February 2023 BOM (Backward Oracle Matching) (Single String Search String Search) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ + $O(mn)$ == Space Complexity == $O(m)$ words (https://link.springer.com/content/pdf/10.1007/3-540-47849-3_18.pdf) == Description == Automaton-based oracle == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-47849-3_18")
- 12:14, 15 February 2023 Boyer-Moore-Horspool (BMH) (Single String Search String Search) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Bad-character heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380100608")
- 12:14, 15 February 2023 Aho–Corasick (AC) Algorithm (Multiple String Search String Search) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m + z)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, finite automaton that tracks the partial prefix match == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://cr.yp.to/bib/1975/aho.pdf")
- 12:14, 15 February 2023 Backward Non-Deterministic DAWG Matching (BNDM) (Single String Search String Search) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(sm)$ words (https://link.springer.com/chapter/10.1007/BFb0030778) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0030778")
- 12:14, 15 February 2023 Commentz-Walter Algorithm (Multiple String Search String Search) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, constructs a converse state machine from the given patterns == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://link.springer.com/chapter/10.1007/3-540-09510-1_10")
- 12:14, 15 February 2023 Fast Hybrid Algorithm (Single String Search String Search) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$+ $O(m+s)$ == Space Complexity == $O(m)$ words (Derived: Uses three tables, each of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://thesai.org/Downloads/Volume8No6/Paper_15-Fast_Hybrid_String_Matching_Algorithm.pdf")
- 12:14, 15 February 2023 Quick-Skip Searching (Single String Search String Search) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses two tables, both of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == http://www.ijcte.org/papers/462-G1278.pdf")
- 12:14, 15 February 2023 String-Matching with Finite Automata (Single String Search String Search) (hist | edit) [275 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: $O(m)$ states in the DFA) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 12:14, 15 February 2023 General number field sieve (Second Category Integer Factoring Integer Factoring) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
- 12:14, 15 February 2023 Two-way String-Matching Algorithm (Single String Search String Search) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m)$ == Space Complexity == $O({1})$ words (http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf")
- 12:14, 15 February 2023 Shor's algorithm Quantum Implementation (Second Category Integer Factoring Integer Factoring) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ qubits (https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 1994 == Reference == https://ieeexplore.ieee.org/document/365700/")
- 12:14, 15 February 2023 Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log(V)$/p) == Space Complexity == $O(V)$ total words (Initializes and uses a constant number of arrays of size O(V) (and does work similar to work done in Boruvka/Prim algorithm)) == Description == Parallel algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM/SMPs? == Year == 2006 == Reference == https://www.sciencedirect.com/science/article/pii/S0743731506001262")
- 12:14, 15 February 2023 Incremental convex hull algorithm; Michael Kallay ( Convex Hull) (hist | edit) [294 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/002001908490084X")
- 12:14, 15 February 2023 Special number field sieve (First Category Integer Factoring Integer Factoring) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == For integers of the form $r^e \pm s$, for r and s relatively small == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
- 12:14, 15 February 2023 Alon and Kahale (3-Graph Coloring Graph Coloring) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.24}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.tau.ac.il/~nogaa/PDFS/spectcolpr1.pdf")
- 12:14, 15 February 2023 Schöning (3-Graph Coloring Graph Coloring) (hist | edit) [260 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.333}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/814612")
- 12:14, 15 February 2023 Johnson (3-Graph Coloring Graph Coloring) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.4422}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019088900658")
- 12:14, 15 February 2023 Hirsch (3-Graph Coloring Graph Coloring) (hist | edit) [273 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.239}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/314613.314838")
- 12:14, 15 February 2023 Ahuja et al. ( Maximum Flow) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELog(V(LogU)$^{0.5} / E)) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf")
- 12:14, 15 February 2023 Wu et al. (LCS Longest Common Subsequence) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$? words (Derived: Same as the above two) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://publications.mpi-cbg.de/Wu_1990_6334.pdf")
- 12:14, 15 February 2023 Robson (3-Graph Coloring Graph Coloring) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2108}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900325")
- 12:14, 15 February 2023 Miller and Myers (LCS Longest Common Subsequence) (hist | edit) [393 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (Derived: Uses an upper triangular matrix $M$ that is size $(m + 1) \times (m + 1)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380151102")
- 12:14, 15 February 2023 Nakatsu et al. (LCS Longest Common Subsequence) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://link.springer.com/article/10.1007/BF00264437")
- 12:09, 15 February 2023 List:Algorithms (hist | edit) [281,464 bytes] Admin (talk | contribs) (Created page with "{| class="wikitable sortable" style="text-align:center;" width="100%" ! Family !! Name !! Year !! Time Complexity !! Space Complexity |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) || 1975 || $O(n)$ || $O(n)$ |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Karpinski (Appro...")
- 11:55, 15 February 2023 Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow (hist | edit) [602 bytes] Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: All-Pairs Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https:/...")
- 11:55, 15 February 2023 Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: Maximum Local Edge Connectivity == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https://dl.acm.org/doi/abs/10.1145/32...")
- 11:55, 15 February 2023 Reduction from MAX-CNF-SAT to st-Maximum Flow (hist | edit) [503 bytes] Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Dynamic $st$-Shortest Path (hist | edit) [661 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic $st$-Shortest Path == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Scien...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Dynamic Bipartite Maximum-Weight Matching (hist | edit) [676 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic Bipartite Maximum-Weight Matching == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of...")
- 11:55, 15 February 2023 Reduction from Triangle Detection to Dynamic Bipartite Maximum-Weight Matching (hist | edit) [767 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic Bipartite Maximum-Weight Matching == Description == == Implications == let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$<br/>if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$<br/>then: Strong Triangle is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply stro...")
- 11:55, 15 February 2023 Reduction from Triangle Detection to Dynamic st-Reach (hist | edit) [791 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic st-Reach == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popula...")
- 11:55, 15 February 2023 Reduction from Triangle Detection to Strong Connectivity (dynamic) (hist | edit) [755 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Strong Connectivity (dynamic) == Description == == Implications == let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$<br/>if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$<br/>then: Strong Triangle is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bou...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Dynamic ST-Reach (hist | edit) [672 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic ST-Reach == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of Com...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Dynamic 4/3-Diameter (hist | edit) [676 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic 4/3-Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Dynamic MaxSCC (hist | edit) [687 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic MaxSCC == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Fou...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Dynamic Connected Subgraph (hist | edit) [699 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic Connected Subgraph == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symp...")
- 11:55, 15 February 2023 Reduction from Min-Weight k-Clique to Minimum Weight k-Cycle (hist | edit) [635 bytes] Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Clique TO: Minimum Weight k-Cycle == Description == == Implications == if: to-time: $O(nm^{\lceil k/{2} \rceil / \lambda - \epsilon})$ for any $\epsilon > {0}$ for $m = \Theta(n^{1+{1}/(\lambda - {1})}) edges and $n$ nodes where $\lambda = k - \lceil k/{2} \rceil + {1}$<br/>then: from-time: $O(n^{k - \epsilon})$ for some $\epsilon > {0}$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Will...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to (hist | edit) [677 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: #SSR == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations o...")
- 11:55, 15 February 2023 Reduction from Min-Weight k-Cycle to Undirected Wiener Index (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Cycle TO: Undirected Wiener Index == Description == == Implications == if: to-time: $f(N,M)$ for N nodes, M edges<br/>then: from-time: $\tilde{O}(f(N,M)+M)$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proc. SODA, page to appear, 2018. https://arxiv.org/pdf/1712.08147v2.pdf, Theorem B.2")
- 11:55, 15 February 2023 Reduction from CNF-SAT to SC2 (hist | edit) [676 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: SC2 == Description == == Implications == if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing<br/>then: SETH is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Positive Betweenness Centrality (hist | edit) [732 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Positive Betweenness Centrality == Description == Positive Betweenness Centrality in directed or undirected graphs with weights in $\{1, 2\}$ == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Approximate Betweenness Centrality (hist | edit) [720 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Approximate Reach Centrality (hist | edit) [688 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Reach Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and d...")
- 11:55, 15 February 2023 Reduction from Betweenness Centrality (BC) to Diameter (hist | edit) [588 bytes] Admin (talk | contribs) (Created page with "FROM: Betweenness Centrality (BC) TO: Diameter == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic Monte-Carlo PTAS == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA...")
- 11:55, 15 February 2023 Reduction from Approximate Betweenness Centrality to Diameter (hist | edit) [556 bytes] Admin (talk | contribs) (Created page with "FROM: Approximate Betweenness Centrality TO: Diameter == Description == $\alpha$-approximation with $\alpha > 1$ == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681...")
- 11:55, 15 February 2023 Reduction from Diameter to Approximate Betweenness Centrality (hist | edit) [556 bytes] Admin (talk | contribs) (Created page with "FROM: Diameter TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation with $\alpha > 1$ == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681...")
- 11:55, 15 February 2023 Reduction from Undirected, Weighted APSP to Undirected All-Nodes Reach Centrality (hist | edit) [601 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected, Weighted APSP TO: Undirected All-Nodes Reach Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Dieg...")
- 11:55, 15 February 2023 Reduction from Undirected, Weighted APSP to Undirected All-Nodes Positive Betweenness Centrality (hist | edit) [616 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected, Weighted APSP TO: Undirected All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Directed All-Nodes Positive Betweenness Centrality (hist | edit) [612 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Directed All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 201...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Directed All-Nodes Reach Centrality (hist | edit) [597 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Directed All-Nodes Reach Centrality == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, C...")
- 11:55, 15 February 2023 Reduction from Reach Centrality to Positive Betweenness Centrality (hist | edit) [704 bytes] Admin (talk | contribs) (Created page with "FROM: Reach Centrality TO: Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diamete...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to All-Nodes Positive Betweenness Centrality (hist | edit) [739 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: All-Nodes Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph ce...")
- 11:55, 15 February 2023 Reduction from Positive Betweenness Centrality to Diameter (hist | edit) [766 bytes] Admin (talk | contribs) (Created page with "FROM: Positive Betweenness Centrality TO: Diameter == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge directed (resp. undirected) graph with integer weights in $(-M,M)$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic eq...")
- 11:55, 15 February 2023 Reduction from Diameter to Positive Betweenness Centrality (hist | edit) [696 bytes] Admin (talk | contribs) (Created page with "FROM: Diameter TO: Positive Betweenness Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Pr...")
- 11:55, 15 February 2023 Reduction from Diameter to Reach Centrality (hist | edit) [681 bytes] Admin (talk | contribs) (Created page with "FROM: Diameter TO: Reach Centrality == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph<br/>then: from-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge directed (resp. undirected) graph == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of th...")
- 11:55, 15 February 2023 Reduction from Undirected, Weighted APSP to All-Nodes Median Parity (hist | edit) [587 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected, Weighted APSP TO: All-Nodes Median Parity == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, Ja...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to All-Nodes Median Parity (hist | edit) [585 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: All-Nodes Median Parity == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, Janu...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to All-Nodes Median Parity (hist | edit) [656 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: All-Nodes Median Parity == Description == == Implications == if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$<br/>then: from-time: $\tilde{O}T(n,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Radius (hist | edit) [643 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Radius == Description == == Implications == if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$<br/>then: from-time: $\tilde{O}(T(n,m,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposi...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Approximate Diameter (hist | edit) [493 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation<br/>then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$ == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://people.csail.mit....")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Betweenness Centrality (BC) (hist | edit) [626 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Betweenness Centrality (BC) == Description == == Implications == if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge graph<br/>then: from-time: $\tilde{O}T(n,m))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Al...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Median (hist | edit) [639 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Median == Description == == Implications == if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$<br/>then: from-time: $\tilde{O}T(n,M))$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium o...")
- 11:55, 15 February 2023 Reduction from Reach Centrality to Diameter (hist | edit) [737 bytes] Admin (talk | contribs) (Created page with "FROM: Reach Centrality TO: Diameter == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10.1137/1.9781611...")
- 11:55, 15 February 2023 Reduction from Undirected Median to Undirected, Weighted APSP (hist | edit) [504 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected Median TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi...")
- 11:55, 15 February 2023 Reduction from Directed Median to Directed, Weighted APSP (hist | edit) [500 bytes] Admin (talk | contribs) (Created page with "FROM: Directed Median TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10....")
- 11:55, 15 February 2023 Reduction from Betweenness Centrality (BC) to Undirected, Weighted APSP (hist | edit) [514 bytes] Admin (talk | contribs) (Created page with "FROM: Betweenness Centrality (BC) TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.si...")
- 11:55, 15 February 2023 Reduction from Betweenness Centrality (BC) to Directed, Weighted APSP (hist | edit) [512 bytes] Admin (talk | contribs) (Created page with "FROM: Betweenness Centrality (BC) TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam...")
- 11:55, 15 February 2023 Reduction from Undirected Radius to Undirected, Weighted APSP (hist | edit) [504 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected Radius TO: Undirected, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi...")
- 11:55, 15 February 2023 Reduction from Nondecreasing Triangle to Triangle in Unweighted Graph (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "FROM: Nondecreasing Triangle TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1")
- 11:55, 15 February 2023 Reduction from Negative Triangle to Price Query (hist | edit) [503 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle TO: Price Query == Description == == Implications == if: to-time: $O(n^{2} / f(n))$ to answer any subsequent price query after $n$-node edge-weighted graph is preprocessed in $O(^k)$ time for some constant $k > {0}$<br/>then: from-time: $O(n^{3} / f(n^{1/({2}k)})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/...")
- 11:55, 15 February 2023 Reduction from Directed Radius to Directed, Weighted APSP (hist | edit) [500 bytes] Admin (talk | contribs) (Created page with "FROM: Directed Radius TO: Directed, Weighted APSP == Description == == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681–1697, 2015. https://epubs.siam.org/doi/10....")
- 11:55, 15 February 2023 Reduction from All-Integers 3SUM to 3SUM (hist | edit) [398 bytes] Admin (talk | contribs) (Created page with "FROM: All-Integers 3SUM TO: 3SUM == Description == == Implications == if: to-time: $O(n^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O(n^{1.5} + n^{2-\epsilon / 2})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 8.1")
- 11:55, 15 February 2023 Reduction from $(\min, \leq)$ Product to Triangle in Unweighted Graph (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "FROM: $(\min, \leq)$ Product TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))} \log n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1")
- 11:55, 15 February 2023 Reduction from 3SUM to All-Integers 3SUM (hist | edit) [177 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: All-Integers 3SUM == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T(n))$ == Year == == Reference == Trivial")
- 11:55, 15 February 2023 Reduction from BMM to Independent Set Queries (hist | edit) [513 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.or...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Second Shortest Simple Path (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(n^{2}W)) \log Wn)$ for graphs with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.114...")
- 11:55, 15 February 2023 Reduction from Distance Product to Second Shortest Simple Path (hist | edit) [503 bytes] Admin (talk | contribs) (Created page with "FROM: Distance Product TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(nW)) \log W)$ for two $n\times n$ matrices with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Replacement Paths Problem (RPP) (hist | edit) [494 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Replacement Paths Problem (RPP) == Description == == Implications == if: to-time: $T(n) polylog M$ in graphs with integer weights in $({0}, M)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3})) polylog M)$ in graphs with integer weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/318...")
- 11:55, 15 February 2023 Reduction from Minimum Triangle to Second Shortest Simple Path (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "FROM: Minimum Triangle TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $T(O(n), O(nW))$ for $n$ node graph with integer weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem...")
- 11:55, 15 February 2023 Reduction from Triangle Detection to Independent Set Queries (hist | edit) [528 bytes] Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. ht...")
- 11:55, 15 February 2023 Reduction from Maximum Subarray to Negative Triangle Detection (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Subarray TO: Negative Triangle Detection == Description == == Implications == == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/abs/10.5555/314613.314823")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Maximum Subarray (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Maximum Subarray == Description == == Implications == == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.4")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Metricity (hist | edit) [494 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Metricity == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$, and $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Shortest Cycle (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Shortest Cycle == Description == == Implications == if: to-time: $T(n,M)$ where there are $n$ nodes and weights in $({1}, M)$<br/>then: from-time: $T(n, O(M))$ where there are $n$ nodes and weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.3")
- 11:55, 15 February 2023 Reduction from Metricity to Negative Triangle Detection (hist | edit) [495 bytes] Admin (talk | contribs) (Created page with "FROM: Metricity TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Undirected, Weighted APSP (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Undirected, Weighted APSP == Description == == Implications == if: to-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$<br/>then: from-time: $T(n, M)$ where graph has weights in $({0}, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1")
- 11:55, 15 February 2023 Reduction from Undirected, Weighted APSP to Directed, Weighted APSP (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: Undirected, Weighted APSP TO: Directed, Weighted APSP == Description == == Implications == if: to-time: $T(n, M)$ where graph has weights in $({0}, M)$<br/>then: from-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1")
- 11:55, 15 February 2023 Reduction from All Pairs Minimum Witness (APMW) to Negative Triangle Detection (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "FROM: All Pairs Minimum Witness (APMW) TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T(n^{1/3})n^{2})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.5")
- 11:55, 15 February 2023 Reduction from Maximum Subarray to Distance Product (hist | edit) [499 bytes] Admin (talk | contribs) (Created page with "FROM: Maximum Subarray TO: Distance Product == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O(n^{3-\epsilon})$ == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/a...")
- 11:55, 15 February 2023 Reduction from Minimum Witness Finding to Negative Triangle Detection (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "FROM: Minimum Witness Finding TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$ where $n$ is the number of nodes in the graph<br/>then: from-time: $O(T(n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.4")
- 11:55, 15 February 2023 Reduction from Negative Triangle Listing to Negative Triangle Detection (hist | edit) [578 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Listing TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{3-\epsilon}\log^c M)$ for some $\epsilon > {0}$ and where $M$ is the maxint of $R$<br/>then: from-time: $O(n^{3-\epsilon'}\log^c M)$ for some $\epsilon' > {0}$ for listing $\Delta = O(n^{3-\delta})$ negative triangles with fixed $\delta > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Betw...")
- 11:55, 15 February 2023 Reduction from BMM to CFG Parsing (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "FROM: BMM TO: CFG Parsing == Description == == Implications == if: to-time: $O(gn^{3-\epsilon})$ for some $\epsilon > {0}$ where $g$ is the size of the CFG and $n$ is the size of the string<br/>then: from-time: $O(n^{3-\epsilon/3})$ where $n \times n$ matrix == Year == 2002 == Reference == L. Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1–15. https://arxiv.org/abs/cs/0112018")
- 11:55, 15 February 2023 Reduction from Negative Triangle Detection to Matrix Product Verification (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Matrix Product Verification == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T({2}n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.1")
- 11:55, 15 February 2023 Reduction from Matrix Product to Negative Triangle Detection (hist | edit) [524 bytes] Admin (talk | contribs) (Created page with "FROM: Matrix Product TO: Negative Triangle Detection == Description == Generic runtimes for two $n \times n$ matrices == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(n^{2} \cdot T(n^{1/3})\log W)$ for two $n\times n$ matrices where $W$ is the maxint of $R$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.o...")
- 11:55, 15 February 2023 Reduction from Negative Triangle Search to Negative Triangle Detection (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "FROM: Negative Triangle Search TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(T(n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.1")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Longest Common Substring with don't cares (hist | edit) [566 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Longest Common Substring with don't cares == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-51. Springe...")
- 11:55, 15 February 2023 Reduction from Directed, Weighted APSP to Negative Triangle Detection (hist | edit) [421 bytes] Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Negative Triangle Detection == Description == == Implications == if: to-time: $n^{3-\epsilon}$ for some $\epsilon >{0}$<br/>then: from-time: $n^{3-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893")
- 11:55, 15 February 2023 Reduction from CFG Parsing to BMM (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "FROM: CFG Parsing TO: BMM == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix<br/>then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG == Year == 1975 == Reference == L. G. Valiant. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308–315. https://www.sciencedirect.com/science/article/pii/S0022000075800468")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Multiple Local Alignment (hist | edit) [607 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Multiple Local Alignment == Description == == Implications == if: to-time: $N^{k-\epsilon}$ for some $\epsilon > {0}$ on $k$ binary strings of length $n$ with $k$-wise scoring<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Langu...")
- 11:55, 15 February 2023 Reduction from CNF-SAT to Local Alignment (hist | edit) [576 bytes] Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Local Alignment == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-5...")
- 11:55, 15 February 2023 Reduction from 3SUM' to Static Dihedral Rotation Queries (hist | edit) [491 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: Static Dihedral Rotation Queries == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2003 == Reference == Michael Soss, Jeff Erickson, Mark Overmars, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry, Volume 26, Issue 3, 2003, Pages 235-246 https://doi.org/10.1016/S0925...")
- 11:55, 15 February 2023 Reduction from 3SUM to Local Alignment (hist | edit) [625 bytes] Admin (talk | contribs) (Created page with "FROM: 3SUM TO: Local Alignment == Description == == Implications == if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$<br/>then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium...")
- 11:55, 15 February 2023 Reduction from Visible Triangle to Triangles Cover Triangle (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Visible Triangle TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 11:55, 15 February 2023 Reduction from Triangles Cover Triangle to Visible Triangle (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Visible Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 11:55, 15 February 2023 Reduction from Triangles Cover Triangle to 3D Motion Planning (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: 3D Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 11:55, 15 February 2023 Reduction from GeomBase to Visibility From Infinity (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Visibility From Infinity == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 11:55, 15 February 2023 Reduction from GeomBase to Planar Motion Planning (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Planar Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
- 11:54, 15 February 2023 Brandes (Weighted Betweenness Centrality (BC)) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm + n^{2} \log n)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249")
- 11:54, 15 February 2023 Brandes (Unweighted Betweenness Centrality (BC)) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249")
- 11:54, 15 February 2023 Dial's Algorithm (nonnegative integer weights Shortest Path (Directed graphs)) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+LV)$ == Space Complexity == $O(V+L)$ words (keep track of vertices and L most recent buckets) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://dl.acm.org/doi/10.1145/363269.363610")
- 11:54, 15 February 2023 Thorup (positive integer weights; assumes constant-time multiplication Shortest Path (Undirected graphs)) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (https://dl.acm.org/doi/10.1145/316542.316548) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://dl.acm.org/doi/10.1145/316542.316548")
- 11:54, 15 February 2023 Gabow et al, Section 3 (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+VlogV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168")
- 11:54, 15 February 2023 Khuller, Matias (k-dimensional space, Euclidean metric Closest Pair Problem) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == infinite (can be upper bounded by $O(n^{2})$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Real RAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub")
- 11:54, 15 February 2023 Tarjan (directed, dense) (Directed (Optimum Branchings), Super Dense MST Minimum Spanning Tree (MST)) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103")
- 11:54, 15 February 2023 Gabow, Galil, Spencer (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VlogV+Eloglog(logV/log(E/V + {2})$)) == Space Complexity == $O(E)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
- 11:54, 15 February 2023 Chu-Liu-Edmonds Algorithm (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(EV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/71b/jresv71bn4p233_a1b.pdf")
- 11:54, 15 February 2023 Tarjan (directed, general) (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103")
- 11:54, 15 February 2023 Fredman & Willard (Undirected, Integer Weights MST Minimum Spanning Tree (MST)) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+V)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Trans-dichotomous == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000005800649?via%3Dihub")
- 11:54, 15 February 2023 Gabow et al, Section 2 (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*log(beta(E, V)$)) == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168")
- 11:54, 15 February 2023 Pettie, Ramachandran (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == unknown but optimal == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/505241.505243")
- 11:54, 15 February 2023 Cheriton-Tarjan (planar) (Undirected, Planar MST Minimum Spanning Tree (MST)) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V)$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051")
- 11:54, 15 February 2023 Cheriton-Tarjan (dense) (Undirected, Dense MST Minimum Spanning Tree (MST)) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051")
- 11:54, 15 February 2023 Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [270 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(V)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==")
- 11:54, 15 February 2023 Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://dl.acm.org/citation.cfm?id=28874")
- 11:54, 15 February 2023 Multistep (SCCs Strongly Connected Components) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}+E)$ == Space Complexity == $O(V+E)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6877288")
- 11:54, 15 February 2023 Geldenhuys-Valmari (SCCs Strongly Connected Components) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$? words ((follow-up from Tarjan's algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6")
- 11:54, 15 February 2023 (many more...) (2-dimensional Convex Hull, Dynamic Convex Hull) (hist | edit) [221 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == == Reference ==")
- 11:54, 15 February 2023 Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ per operation, $O(n*log(n)$) total == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/abs/10.1145/359131.359132")
- 11:54, 15 February 2023 Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/002200008190012X?via%3Dihub")
- 11:54, 15 February 2023 Chand-Kapur, Gift Wrapping (d-dimensional Convex Hull Convex Hull) (hist | edit) [286 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f_1)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1970 == Reference == https://dl.acm.org/doi/pdf/10.1145/321556.321564")
- 11:54, 15 February 2023 N-dimensional Quickhull (d-dimensional Convex Hull Convex Hull) (hist | edit) [353 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f(h)$/h) where f(h) denotes the maximum number of facets with h vertices == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/pdf/10.1145/235815.235821")
- 11:54, 15 February 2023 Jiang, Song, Weinstein and Zhang ( Linear Programming) (hist | edit) [462 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication; currently $O(n^{2.37285956})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/1810.07896")
- 11:54, 15 February 2023 NIEVERGELT. J.. AND PREPARATA (Section 2) (Reporting all intersection points / general polygons Line segment intersection) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((n+k)$log n) == Space Complexity == $O(n+k)$ words (https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1982 == Reference == https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf")
- 11:54, 15 February 2023 Seidel's Shelling Algorithm (d-dimensional Convex Hull Convex Hull) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}+f_1*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://dl.acm.org/doi/pdf/10.1145/12130.12172")
- 11:54, 15 February 2023 Vaidya ( Linear Programming) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) == Space Complexity == $O((nm+n^{2})$L)? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01580859")
- 11:54, 15 February 2023 CHAZELLE 1986 (Counting number of intersection points / line segments Line segment intersection) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.695})$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000086900255) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0022000086900255")
- 11:54, 15 February 2023 Parameter-expanded expectation maximization (PX-EM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == http://www.stat.ucla.edu/~ywu/research/papers/PXEM.pdf")
- 11:54, 15 February 2023 Asymptotically fast Toeplitz algorithms (Toeplitz Linear system of equations) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log^{2}(n)$) == Space Complexity == $O(n*log^{2}(n)$)? words (upper bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008? == Reference == https://epubs.siam.org/doi/10.1137/040617200")
- 11:54, 15 February 2023 Matrix inverse (General Linear system of equations) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on the complexity of matrix multiplication;<br/>currently $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (equivalent to matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
- 11:54, 15 February 2023 Peng, Vempala (Sparse Linear system of equations) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(max(m^{(omega-{2})/(omega-{1})}*n^{2}, n^{({5}*omega-{4})/(omega+{1})})*log^{2}(k/epsilon))$ where omega is the exponent on the complexity of matrix multiplication; currently $O(n^{2.331642})$ == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/2007.10254")
- 11:54, 15 February 2023 LU decomposition (General Linear system of equations) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O (n^{3}) == Space Complexity == $O(n^{2})$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 3 ( Chromatic Polynomial) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) => $O({1.292}^n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Koivisto ( Chromatic Polynomial) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
- 11:54, 15 February 2023 Fürer, Kasiviswanathan ( (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7702}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.634.4498&rep=rep1&type=pdf")
- 11:54, 15 February 2023 Fomin; Gaspers & Saurabh ( (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.6262}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9")
- 11:54, 15 February 2023 Zykov (deletion-contraction) ( Chromatic Polynomial) (hist | edit) [253 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((({1}+sqrt5)$/{2})^(n+m)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1949 == Reference ==")
- 11:54, 15 February 2023 Angelsmark, Jonsson ( (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7879}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45193-8_6")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( Chromatic Number) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Koivisto ( Chromatic Number) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( Chromatic Number) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 BFS/DFS for connected components ( (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ == Space Complexity == $O(n)$ auxiliary words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==")
- 11:54, 15 February 2023 Eppstein ( Chromatic Number) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({4}/{3}+{3}^({4}/{3})$/{4})^n) ~ $O({2.4151}^n)$ == Space Complexity == $O({2}^n)$ words (https://arxiv.org/pdf/cs/0011009.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://arxiv.org/pdf/cs/0011009.pdf")
- 11:54, 15 February 2023 Byskov ( Chromatic Number) (hist | edit) [407 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({80}^(n/{5})$) ~ $O({2.4023}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/pii/S0167637704000409")
- 11:54, 15 February 2023 Lawler ( Chromatic Number) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn({1}+{3}^({1}/{3})$)^n) == Space Complexity == $O({2}^n*log(n)$) words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
- 11:54, 15 February 2023 Zamir ( 6 - Graph Coloring) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
- 11:54, 15 February 2023 Christofides ( Chromatic Number) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!*poly(n)$) == Space Complexity == $O(poly(n)$) words (https://link.springer.com/article/10.1007/s00453-007-9149-8) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://academic.oup.com/comjnl/article/14/1/38/356253?login=true")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( 6 - Graph Coloring) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Byskov, Theorem 20 ( 6 - Graph Coloring) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2680}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 11:54, 15 February 2023 Byskov, Theorem 14 ( 6 - Graph Coloring) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.3289}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( 6 - Graph Coloring) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Zamir ( 5 - Graph Coloring) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Proposition 2 ( 5 - Graph Coloring) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Bjorklund, Husfeldt, Theorem 1 ( 5 - Graph Coloring) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
- 11:54, 15 February 2023 Method of Four Russians ( Matrix Multiplication) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}/log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=On+economical+construction+of+the+transitive+closure+of+an+oriented+graph.&btnG=")
- 11:54, 15 February 2023 Alman, Vassilevska Williams ( Matrix Multiplication) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (through re-use of space in recursive branches (response from Virginia)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/pdf/2010.05846.pdf")
- 11:54, 15 February 2023 Byskov ( 5 - Graph Coloring) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.1592}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
- 11:54, 15 February 2023 Chen et al ( Maximum Flow) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)*log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2022 == Reference == https://arxiv.org/abs/2203.00671")
- 11:54, 15 February 2023 Gao, Liu, Peng ( Maximum Flow) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.07233")
- 11:54, 15 February 2023 Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.66} log(V)$ log(U)) == Space Complexity == $O(V^{2})$ words (https://dl.acm.org/citation.cfm?id=290181) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181")
- 11:54, 15 February 2023 Brand et al ( Maximum Flow) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((E+V^{1.5})$log(U)polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.05719")
- 11:54, 15 February 2023 Lee, Sidford ( Maximum Flow) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6979027")
- 11:54, 15 February 2023 Madry ( Maximum Flow) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7782974")
- 11:54, 15 February 2023 Kathuria, Liu, Sidford ( Maximum Flow) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)/sqrt(eps)) == Space Complexity == $O(E)$ or $O(V^{2})$ ? words (unsure, please look) == Description == == Approximate? == Approximate Approximation Factor: 1+eps == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://epubs.siam.org/doi/abs/10.1137/20M1383525")
- 11:54, 15 February 2023 Shiloach ( Maximum Flow) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3}*log(V)$/p) == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM (unclear what type; seems like any could work?) == Year == 1981 == Reference == http://users.umiacs.umd.edu/~vishkin/TEACHING/4CLASS/SV82-maxflow.pdf")
- 11:54, 15 February 2023 MKM Algorithm ( Maximum Flow) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://eprints.utas.edu.au/160/1/iplFlow.pdf")
- 11:54, 15 February 2023 Galil ( Maximum Flow) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^({5}/{3})$E^({2}/{3})) == Space Complexity == $O(E)$ words (https://link.springer.com/article/10.1007/BF00264254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://link.springer.com/article/10.1007/BF00264254")
- 11:54, 15 February 2023 Gabow ( Maximum Flow) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE*logU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://www.sciencedirect.com/science/article/pii/002200008590039X")
- 11:54, 15 February 2023 Parallel Merge Sort - Cole (1) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 11:54, 15 February 2023 Parallel Merge Sort - Cole (2) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 11:54, 15 February 2023 ( Negative Triangle) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.5")
- 11:54, 15 February 2023 Larsen, Williams (follows from Theorem 2.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^({11}/{4})$ / sqrt(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Cell Probe == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 11:54, 15 February 2023 Williams ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / (log n)$^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == http://www.cs.cmu.edu/~./theorylunch/pastSemesterIndices/slides/20070117.pdf")
- 11:54, 15 February 2023 Larsen, Williams (Theorem 1.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / {2}^(Omega(sqrt(log n)$))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 11:54, 15 February 2023 Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{3} / log^{3} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = log n == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.16")
- 11:54, 15 February 2023 Yu (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}*poly(log log n)$/log^{4} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = Omega(log n) == Year == 2015 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540118300099")
- 11:54, 15 February 2023 Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{2} / log^{2.25} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM with word size w = log n == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/5438580")
- 11:54, 15 February 2023 Method of Four Russians (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}/(log n)$^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=On+economical+construction+of+the+transitive+closure+of+an+oriented+graph.&btnG=")
- 11:54, 15 February 2023 (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / log^{2.25} n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.4")
- 11:54, 15 February 2023 Cygan, Gabow, Sankowski (Bounded integer weights Graph Diameter) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(M*V^omega*polylog(M, V)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == https://dl.acm.org/doi/abs/10.1145/2736283")
- 11:54, 15 February 2023 O'Neil 1973 (Boolean Matrix Multiplication Matrix Product) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://core.ac.uk/download/pdf/82467126.pdf")
- 11:54, 15 February 2023 Output-Sensitive Quantum BMM (Boolean Matrix Multiplication Matrix Product) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\}) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Quantum == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.6")
- 11:53, 15 February 2023 Ausiello et al. (Maximum Cut, Approximate Maximum Cut) (hist | edit) [516 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} logE)$ == Space Complexity == $O(V^{2})$? words (Each vertex keeps track of O(V)-sized vector. assuming this is the goemans-williamson algorithm) == Description == == Approximate? == Approximate Approximation Factor: ~0.878; assuming this is the goemans-williamson algorithm == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/content/pdf/1...")
- 11:53, 15 February 2023 Mitzenmacher & Upfal (Maximum Cut, Approximate Maximum Cut) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://lib.ysu.am/open_books/413311.pdf")
- 11:53, 15 February 2023 Motwani & Raghavan (Maximum Cut, Approximate Maximum Cut) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V)$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/random assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1995 == Reference == https://rajsain.files.wordpress.com/2013/11/randomized-algorithms-motwani-and-raghavan.pdf")
- 11:53, 15 February 2023 Khuller; Raghavachari & Young, "Greedy Methods" (Maximum Cut, Approximate Maximum Cut) (hist | edit) [484 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Handbook%20of%20Approximation%20Algorithms%20and%20Metaheuristics%20%5BGonzalez%...")
- 11:53, 15 February 2023 Hadlock (Maximum Cut Maximum Cut) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^V)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
- 11:53, 15 February 2023 Iterative naive (d-Neighborhood of a String d-Neighborhood of a String) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(f_{bin}(sigma-{1}, n, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i == Space Complexity == $O(n)$ auxiliary words (Keep track of which indices the differing letters are on, along with which set of letters are replacing the letters in these indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == http://rosalind.info/...")
- 11:53, 15 February 2023 MATSF (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? (per node) words (Each node needs to keep track of O(1) information about itself, and O(1) information per neighbor for synchronization purposes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM (per node) == Year == 2004 == Reference == https://ieeexplore.ieee.org/document/4359404")
- 11:53, 15 February 2023 Nordbeck and Rystedt (Orientation) (Point-in-Polygon Point-in-Polygon) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of current side being looked at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1967 == Reference == https://doi.org/10.1007/BF01934125")
- 11:53, 15 February 2023 ASP (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (per node) words (Each node needs to keep track of O(1) information about itself, and O(1) information per neighbor for synchronization purposes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM (per node) == Year == 2005 == Reference == https://ieeexplore.ieee.org/document/1281624")
- 11:53, 15 February 2023 Clock-sampling mutual network synchronization (Clock Synchronization in Distributed Systems Clock Synchronization in Distributed Systems) (hist | edit) [515 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? (per node) words (Only needs to keep track of multiplicative correction $s$, its own clocks, and possibly O(1) other info) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM (per node) == Year == 2007 == Reference == https://www.researchgate.net/publication/224306349_Clock-Sampling_Mutual_Network_Synchronization_for_M...")
- 11:53, 15 February 2023 Preparata and Shamos (Wedge) (Point-in-Polygon Point-in-Polygon) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (https://ir.nctu.edu.tw/bitstream/11536/749/1/A1997WM15100010.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1985 == Reference == http://www.cs.kent.edu/~dragan/CG/CG-Book.pdf")
- 11:53, 15 February 2023 Preparata and Shamos (Intersection sum of angle) (Point-in-Polygon Point-in-Polygon) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of current angle and cumulative angle sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1985 == Reference == http://www.cs.kent.edu/~dragan/CG/CG-Book.pdf")
- 11:53, 15 February 2023 Nordbeck and Rystedt (Sum of area) (Point-in-Polygon Point-in-Polygon) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of current triangle and total area sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1967 == Reference == https://doi.org/10.1007/BF01934125")
- 11:53, 15 February 2023 Saalfeld (Sign of offset) (Point-in-Polygon Point-in-Polygon) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of current sides (2) being looked at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1987 == Reference == https://doi.org/10.1080/02693798708927823")
- 11:53, 15 February 2023 Nordbeck and Rystedt (Grid Method) (Point-in-Polygon Point-in-Polygon) (hist | edit) [338 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(a)$ == Space Complexity == $O({1})$ words (Only need to keep track of the current grid square being checked (assuming the set of squares is given in the input)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1967 == Reference == https://doi.org/10.1007/BF01934125")
- 11:53, 15 February 2023 Salomon (Swath Method) (Point-in-Polygon Point-in-Polygon) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (https://ir.nctu.edu.tw/bitstream/11536/749/1/A1997WM15100010.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1978 == Reference == https://doi.org/10.1016/0098-3004(78)90085-7")
- 11:53, 15 February 2023 Ray casting algorithm Shimrat; M (Point-in-Polygon Point-in-Polygon) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Only need to keep track of ray direction and how many polygon sides intersect with the ray) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1962 == Reference == https://dl.acm.org/doi/pdf/10.1145/368637.368653")
- 11:53, 15 February 2023 Brute force (Cyclic Peptide Sequencing Problem Cyclic Peptide Sequencing Problem) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == ${2}^{O(n)}$ == Space Complexity == $O(n)$? words (Keeps track of current amino acid sequence being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1987 == Reference ==")
- 11:53, 15 February 2023 Branch and bound (Cyclic Peptide Sequencing Problem Cyclic Peptide Sequencing Problem) (hist | edit) [399 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == ${2}^{O(n)}$ == Space Complexity == $O({2}^{O(n)})$? words (Keeps track of all possible not fully expanded amino acid sequences so far) == Description == Improvement on brute force (despite not doing better asymptotically) == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1993 == Reference ==")
- 11:53, 15 February 2023 Chubby (Mike Burrows) (Distributed Locking Algorithms Distributed Locking Algorithms) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(f)$? words (Generally need to keep track of one lock per file (exclusivity)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/doi/10.5555/1298455.1298487")
- 11:53, 15 February 2023 Leases (Cary G Gray and David R Cheriton) (Distributed Locking Algorithms Distributed Locking Algorithms) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(f)$? words (Generally need to keep track of one lease/lock per file (exclusivity)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference == https://web.stanford.edu/class/cs240/readings/89-leases.pdf")
- 11:53, 15 February 2023 Achlioptas (Link Analysis Link Analysis) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn )$ == Space Complexity == $O((n+l)$^{2})? words (Computes a constant number of SVDs of O((n+l)^2)-sized matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://homes.cs.washington.edu/~karlin/papers/web-search.pdf")
- 11:53, 15 February 2023 Tushar Deepak Chandra and Sam Toueg (Distributed Locking Algorithms Distributed Locking Algorithms) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p225-chandra.pdf")
- 11:53, 15 February 2023 Richardson and Domingos (Link Analysis Link Analysis) (hist | edit) [381 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(nl)$ words (See paper (noting that sum d_q can be as high as O(nl))) == Description == Query-dependent PageRank == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://homes.cs.washington.edu/~pedrod/papers/nips01b.pdf")
- 11:53, 15 February 2023 Tomlin (Link Analysis Link Analysis) (hist | edit) [465 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(n)$? words (Generally computes O(n) values per iteration (row + column sums and their ratios); algorithm can be smart about intermediate calculations as to not use more space asymptotically) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/775152.775202")
- 11:53, 15 February 2023 Randomized HITS (Link Analysis Link Analysis) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m nlogn )$ == Space Complexity == $O(n)$ words (Stores and updates hub and authority values per node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://dl.acm.org/doi/pdf/10.1145/383952.384003")
- 11:53, 15 February 2023 Haveliwala (Link Analysis Link Analysis) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(nz)$? words (Stores and updates z O(n)-sized vectors designed to converge to some stationary distributions) == Description == PageRank with categories/topics == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == http://www-cs-students.stanford.edu/~taherh/papers/topic-sensitive-pagerank.pdf")
- 11:53, 15 February 2023 PHITS Coheng Chan (Link Analysis Link Analysis) (hist | edit) [461 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(nz)$? words (Needs to store P(z), P(d|z), and P(c|z) after each EM iteration (algorithm can be smart about intermediate calculations as to not use more than O(nz) space)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == http://web.cse.msu.edu/~cse960/Papers/LinkAnalysis/phits.pdf")
- 11:53, 15 February 2023 Jeh and Widom (Link Analysis Link Analysis) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(nh)$ words (Stores and updates z O(n)-sized vectors designed to converge to some basis vectors) == Description == Personalized PageRank with hubs == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == http://infolab.stanford.edu/~glenj/spws.pdf")
- 11:53, 15 February 2023 The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm (Link Analysis Link Analysis) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m^{2} n )$ == Space Complexity == $O(n)$? words (Stores and updates two O(n)-sized vectors (corresponding to 2 random walks) designed to converge to some sort of stationary distribution) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://dl.acm.org/doi/abs/10.1145/382979.383041")
- 11:53, 15 February 2023 Kleinberg (Link Analysis Link Analysis) (hist | edit) [325 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m^{2} n )$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.585.7341&rep=rep1&type=pdf")
- 11:53, 15 February 2023 The INDEGREE Algorithm (InDegree Analysis Link Analysis) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m^{2} n )$ == Space Complexity == $O(n)$ words (Must maintain a list of visited nodes to eliminate duplication.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.w3.org/People/Massimo/papers/quest_hypersearch.pdf")
- 11:53, 15 February 2023 Naive (All Maximal Non-Branching Paths in a Graph All Maximal Non-Branching Paths in a Graph) (hist | edit) [443 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ == Space Complexity == $O(n)$ auxiliary? words (For each vertex, store whether that vertex is a 1-in-1-out vertex (all of these can be pre-computed at the same time in $O(m)$ time). Unclear if there's a better bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == http://rosalind.info/problems/ba3m/")
- 11:53, 15 February 2023 The (Hyperlink-Induced Topic Search) HITS Algorithm (Link Analysis Link Analysis) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Stores and updates hub and authority values per node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.1145/324133.324140")
- 11:53, 15 February 2023 The PAGERANK Algorithm (Link Analysis Link Analysis) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m n )$ == Space Complexity == $O(n)$ words (Stores and updates an O(n)-sized vector designed to converge to some sort of stationary distribution) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf")
- 11:53, 15 February 2023 Sagot M ( Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn m^{1.{4}5})$ == Space Complexity == $O(mn^{2}/w)$ words (https://link.springer.com/chapter/10.1007/BFb0054337) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337")
- 11:53, 15 February 2023 Liang Cwinnower ( Motif Search) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm^{0.5})$ == Space Complexity == $O(m^{2})$ words (Considers a graph on $O(m)$ nodes and $O(m^2)$ edges) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.worldscientific.com/doi/10.1142/S0219720004000466")
- 11:53, 15 February 2023 Bailey TL; Elkan C MEME ( Motif Search) (hist | edit) [407 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}m^{2})$ == Space Complexity == $O(nm)$ words (Uses iterations of the EM algorithm as in (Lawrence, Reilly 1990), and thus uses similar amounts of space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://link.springer.com/article/10.1007/BF00993379")
- 11:53, 15 February 2023 Kingsford ( Motif Search) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m^{2}n^{2})$ words (Creates an ILP with $O(m^2n^2)$ variables and $O(n^2m)$ constraints, each involving $O(m)$ variables) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11780441_22")
- 11:53, 15 February 2023 Sinha S; Tompa M YMF (Yeast Motif Finder) ( Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{0.{6}6} m)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/10977095")
- 11:53, 15 February 2023 Van Helden J; Rios AF; Collado-Vides J ( Motif Search) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == Dyad analysis == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC102821/")
- 11:53, 15 February 2023 Tompa M ( Motif Search) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(m^{2})$ words (Requires considering an $O(m^2)*O(m^2)$ matrix with $O(m^2)$ nonzero entries, based on a DFA with $O(m^2)$ states) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://www.aaai.org/Papers/ISMB/1999/ISMB99-030.pdf")
- 11:53, 15 February 2023 Brute force ( The Set-Covering Problem) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(U {2}^n)$ == Space Complexity == $O(U)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference ==")
- 11:53, 15 February 2023 Helden Oligo-Analysis ( Motif Search) (hist | edit) [431 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(m)$ words (Derived: store number of occurances for each motif of a specified length) == Description == Uses oligonucleotides? Also only detects "short" motifs, and used for yeast == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9719638")
- 11:53, 15 February 2023 Dinur & Steurer ( The Set-Covering Problem) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2013 == Reference == https://www.dsteurer.org/paper/productgames.pdf")
- 11:53, 15 February 2023 Cardoso; Nuno; Abreu; Rui ( The Set-Covering Problem) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2014 == Reference == https://www.semanticscholar.org/paper/An-efficient-distributed-algorithm-for-computing-Cardoso-Abreu/ce32696c1176800c5b90fab026bf93f282e2b161")
- 11:53, 15 February 2023 Feige ( The Set-Covering Problem) (hist | edit) [292 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://courses.cs.duke.edu/spring07/cps296.2/papers/p634-feige.pdf")
- 11:53, 15 February 2023 Raz & Safra ( The Set-Covering Problem) (hist | edit) [280 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log^{3} n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://dl.acm.org/doi/10.1145/258533.258641")
- 11:53, 15 February 2023 Lund & Yannakakis ( The Set-Covering Problem) (hist | edit) [264 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://doi.org/10.1145%2F185675.306789")
- 11:53, 15 February 2023 Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem) (hist | edit) [345 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(U)$ words () == Description == ILP == Approximate? == Approximate Approximation Factor: \log n == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://link.springer.com/chapter/10.1007/978-3-662-04565-7_13")
- 11:53, 15 February 2023 Puterman Modified Policy Iteration (MPI) (Optimal Policies for MDPs Optimal Policies for MDPs) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference ==")
- 11:53, 15 February 2023 Bellman Value Iteration (VI) (Optimal Policies for MDPs Optimal Policies for MDPs) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1957 == Reference == https://www.jstor.org/stable/24900506")
- 11:53, 15 February 2023 Greedy Algorithm ( The Set-Covering Problem) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log n)$ == Space Complexity == $O(U)$ words () == Description == == Approximate? == Approximate Approximation Factor: \ln(n) - \ln(\ln(n)) + \Theta(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/237814.237991")
- 11:53, 15 February 2023 Howard Policy Iteration (PI) (Optimal Policies for MDPs Optimal Policies for MDPs) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == http://web.mit.edu/dimitrib/www/dpchapter.pdf")
- 11:53, 15 February 2023 Ocone (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [287 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/978-1-4612-1784-8_28")
- 11:53, 15 February 2023 Del Moral; Pierre (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [436 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == https://projecteuclid.org/journals/annals-of-applied-probability/volume-8/issue-2/Measure-valued-processes-and-interacting-particle-systems-Application-to-nonlinear/10.1214/aoap/1028903535.full")
- 11:53, 15 February 2023 Maybeck; Peter S Extended Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == $O(n^{2})$? words (Generally works with a constant number of O(n)*O(n)-sized matrices per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference ==")
- 11:53, 15 February 2023 Zakai (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://link.springer.com/article/10.1007/BF00536382")
- 11:53, 15 February 2023 Damiano Brigo; Bernard Hanzon and François LeGland (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.45} logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == https://ieeexplore.ieee.org/abstract/document/661075")
- 11:53, 15 February 2023 Kushner non-linear filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [441 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$?? words (Generally works with a constant number of non-linear transformations; assumes that the description of the non-linear transformations is O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1967 == Reference == https://ieeexplore.ieee.org/document/1098671")
- 11:53, 15 February 2023 Stratonovich (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1959 == Reference ==")
- 11:53, 15 February 2023 Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [331 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Generally works with a constant number of O(n)*O(n)-sized matrices per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference ==")
- 11:53, 15 February 2023 Particle filter Del Moral (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) (hist | edit) [348 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(nN)$? words (Works with O(N) number of O(n)-sized vectors (containing information about particles) each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference ==")
- 11:53, 15 February 2023 LU Matrix Decomposition (Matrix Factorization Collaborative Filtering) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1945 == Reference ==")
- 11:53, 15 February 2023 Cholesky Decomposition (Matrix Factorization Collaborative Filtering) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1983 == Reference ==")
- 11:53, 15 February 2023 QR Matrix Decomposition (Matrix Factorization Collaborative Filtering) (hist | edit) [307 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1955 == Reference ==")
- 11:53, 15 February 2023 Α-EM Algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [518 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://waseda.pure.elsevier.com/en/publications/the-%CE%B1-em-algorithm-surrogat...")
- 11:53, 15 February 2023 Expectation conditional maximization either (ECME) (Liu; Chuanhai; Rubin; Donald B) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://www.jstor.org/stable/2337067")
- 11:53, 15 February 2023 Expectation conditional maximization (ECM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [476 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1993 == Reference == https://academic.oup.com/biomet/article-abstract/80/2/267/251605?redirectedFrom=fulltext")
- 11:53, 15 February 2023 Shaban; Amirreza; Mehrdad; Farajtabar (Maximum Likelihood Methods in Unknown Latent Variables; multi-view model, discrete observations Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == $O(kd+d^{3})$?? words (vector of parameters has size at least Theta(kd), and tensor M has size at least Theta(d^3) in paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2015 == Reference == https://faculty.cc.gatech.edu/~bboots3/files/SpectralExteriorPoint-NIPSWorkshop.pdf")
- 11:53, 15 February 2023 Alpha-HMM (Matsuyama, Yasuo) (Maximum Likelihood Methods in Unknown Latent Variables, Hidden Markov Models Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [302 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2011 == Reference == https://ieeexplore.ieee.org/abstract/document/7895145")
- 11:53, 15 February 2023 Expectation-Maximization (EM) algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875")
- 11:53, 15 February 2023 EM with Quasi-Newton Methods (Jamshidian; Mortaza; Jennrich; Robert I.) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) [481 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{3} n)$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta and Hessian matrix guess, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1997 == Reference == https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/1467-9868....")
- 11:53, 15 February 2023 BEN-CHEN M.; GOTSMAN C.; BUNIN G. 2008 (Mesh Parameterization Mesh Parameterization) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == http://www.cs.technion.ac.il/~gotsman/AmendedPubl/Miri/EG08_Conf.pdf")
- 11:53, 15 February 2023 SPRINGBORN B.; SCHROEDER P.; PINKALL U. 2008 (Mesh Parameterization Mesh Parameterization) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://dl.acm.org/doi/10.1145/1399504.1360676")
- 11:53, 15 February 2023 YANG Y.; KIM J.; LUO F.; HU S.; GU X. 2008 (Mesh Parameterization Mesh Parameterization) (hist | edit) [229 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nloglogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference ==")
- 11:53, 15 February 2023 YOSHIZAWA S.; BELYAEV A. G.; SEIDEL H.-P 2004 (Mesh Parameterization Mesh Parameterization) (hist | edit) [454 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://www.researchgate.net/profile/Alexander_Belyaev5/publication/47861414_A_fast_and_simple_stretch-minimizing_mesh_parameterization/links/5b962a6292851c78c40c0c3f/A-fast-and-simple-stretch-minimizing-mesh-parameterization.pdf")
- 11:53, 15 February 2023 ZAYER R.; ROESSL C.; SEIDEL H.-P 2005 (Mesh Parameterization Mesh Parameterization) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.226.1150&rep=rep1&type=pdf")
- 11:53, 15 February 2023 CHEN Z. G.; LIU L. G.; ZHANG Z. Y.; WANG G. J. 2007 (Mesh Parameterization Mesh Parameterization) (hist | edit) [271 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://dl.acm.org/doi/10.1145/1236246.1236287")
- 11:53, 15 February 2023 SANDER P. V.; SNYDER J.; GORTER S. J.; HOPPE 2001 (Mesh Parameterization Mesh Parameterization) (hist | edit) [273 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/pdf/10.1145/383259.383307")
- 11:53, 15 February 2023 YAN J. Q.; YANG X.; SHI P. F 2006 (Mesh Parameterization Mesh Parameterization) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference ==")
- 11:53, 15 February 2023 ZAYER R.; LÉVY B.; SEIDEL H.-P. 2007 (Mesh Parameterization Mesh Parameterization) (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://dl.acm.org/doi/10.5555/1281991.1282010")
- 11:53, 15 February 2023 HORMANN K.; GREINER G 1999 (Mesh Parameterization Mesh Parameterization) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.semanticscholar.org/paper/MIPS%3A-An-Efficient-Global-Parametrization-Method-Hormann-Greiner/a2f7f69b37565eb2729b45a7d72c6aae2e4908b8")
- 11:53, 15 February 2023 KARNI Z.; GOTSMAN C.; GORTLER S. J. 2005 (Mesh Parameterization Mesh Parameterization) (hist | edit) [324 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://dash.harvard.edu/bitstream/handle/1/2634388/Gortler_FreeBoundary.pdf?sequence=2&isAllowed=y")
- 11:53, 15 February 2023 SHEFFER A.; DE STURLER E. 2000 (Mesh Parameterization Mesh Parameterization) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://link.springer.com/article/10.1007/PL00013391")
- 11:53, 15 February 2023 SHEFFER A.; LÉVY B.; MOGILNITSKY M.; BOGOMYAKOV A. 2005 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://hal.inria.fr/inria-00105689/document")
- 11:53, 15 February 2023 DESBRUN M.; MEYER M.; ALLIEZ P. 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/566654.566588")
- 11:53, 15 February 2023 LÉVY B.; PETITJEAN S.; RAY N.; MAILLOT J 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2.5} n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://members.loria.fr/Bruno.Levy/papers/LSCM_SIGGRAPH_2002.pdf")
- 11:53, 15 February 2023 FLOATER 2003 (Mesh Parameterization Mesh Parameterization) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01466-7/S0025-5718-02-01466-7.pdf")
- 11:53, 15 February 2023 Hentenryck et. al. (Arc Consistency? Stable Matching Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$? words (https://www.sciencedirect.com/science/article/abs/pii/000437029290020X) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/abs/pii/000437029290020X")
- 11:53, 15 February 2023 Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf")
- 11:53, 15 February 2023 Manlove; Malley (Stable Marriage Problem Stable Matching Problem) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~davidm/pubs/7981.pdf")
- 11:53, 15 February 2023 Irving's Algorithm (Stable Roommates Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Manipulates the $O(n)$-many $O(n)$-size preference lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf")
- 11:53, 15 February 2023 Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [517 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is $O(n)$ so the total number of terms to keep track of is $O(n)$. Also, polynomials in the separating set can be computed in $O(n)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.co...")
- 11:53, 15 February 2023 Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is O(n) so the total number of terms to keep track of is O(n). Also, computing h^{((q^d-1)/2)}-1 mod f only requires O(n) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.ams.org/journals/mcom/1...")
- 11:53, 15 February 2023 Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(N)$? words (Computes and stores constant number of polynomials of degree $O(N)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1054260")
- 11:53, 15 February 2023 Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} + nlogn)$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration. Note that computing $gcd(f, x^{(q^i)}-x)$ can be cleverly done in $O(n)$ space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1944 == Reference == -")
- 11:53, 15 February 2023 Schubert's algorithm ( Factorization of Polynomials Over Finite Fields) (hist | edit) [245 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 11:53, 15 February 2023 Square-free factorization (Square-free Factorization of Polynomials Over Finite Fields) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == -")
- 11:53, 15 February 2023 Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Computes the remainder of $g^{((p-1)/2)}-1 mod f$ (in order to find gcd of $g^{((p-1)/2)}-1$ and f)) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1967 == Reference == https://ieeexplore.ieee.org/document/6768643/")
- 11:53, 15 February 2023 Jalali and T. Weissman (Lossy Compression Data Compression) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: Auxiliary data structures are H_k and m_k. H_k is just a singular value and is constant space, but m_k is a O(n)-size vector.) == Description == Gibbs sampler == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://web.stanford.edu/~tsachy/pdf_files/Lossy%20Source%20Coding%20via%20Markov%20Cha...")
- 11:53, 15 February 2023 Miyake 2006 (Lossy Compression Data Compression) (hist | edit) [483 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://www.semanticscholar.org/paper/Lossy-Data-Compression-over-Zq-by-LDPC-Code-Miyake/652f0438118898b63126f7261ec4cd2002ff0e0b")
- 11:53, 15 February 2023 Jalali; A. Montanari; and T. Weissman (Lossy Compression Data Compression) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://authors.library.caltech.edu/17983/1/Jalali2010p7459Ieee_T_Inform_Theory.pdf")
- 11:53, 15 February 2023 Korada and R. Urbanke; (Lossy Compression Data Compression) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(N)$ words (Derived: size of the polar codes that need to be stored) == Description == Polar codes == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/0903.0307.pdf")
- 11:53, 15 February 2023 Martinian and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://arxiv.org/abs/cs/0602046")
- 11:53, 15 February 2023 Brute force (Lossy Compression Data Compression) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
- 11:53, 15 February 2023 Ciliberti; Mézard (Lossy Compression Data Compression) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == Constraint Satisfaction Problem with Random Gates == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://arxiv.org/abs/cond-mat/0504509")
- 11:53, 15 February 2023 Maneva and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ bits (Derived: size of the factor graph representation of the generator matrix, or size of the generator matrix itself) == Description == Low Density Generator Matrix (LDGM) codes; for a Bernouli(1/2) source == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://ieeexplore.ieee.org/document/1523592")
- 11:53, 15 February 2023 Sun; M. Shao; J. Chen; K. Wong; and X. Wu (Lossy Compression Data Compression) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5474629/")
- 11:53, 15 February 2023 Discrete Cosine Transform (Lossy Compression Data Compression) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store the DCT coefficient for each input term) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://doi.org/10.1109%2FT-C.1974.223784")
- 11:53, 15 February 2023 Matsunaga; Yamamoto (Lossy Compression Data Compression) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == exp(n) words (https://doi.org/10.1109/TIT.2003.815805) == Description == Low Density Parity Check (LDPC) == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://doi.org/10.1109/TIT.2003.815805")
- 11:53, 15 February 2023 Gupta; Verdu (Lossy Compression Data Compression) (hist | edit) [449 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{3} n)$ == Space Complexity == $O(n)$ bits (Derived: Considering the codebook to be part of the input, this only requires storing a single codeword in memory, of size $O(n)$, along with some constants) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://doi.org/10.1109/TIT.2009.2016040")
- 11:53, 15 February 2023 The Multihash Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 11:53, 15 February 2023 The Multistage Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 11:53, 15 February 2023 A-Priori algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://dl.acm.org/doi/pdf/10.1145/1014052.1014091) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == http://www.vldb.org/conf/1994/P487.PDF")
- 11:53, 15 February 2023 The Algorithm of Park; Chen; and Yu (PCY) (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://dl.acm.org/doi/abs/10.1145/568271.223813")
- 11:53, 15 February 2023 GLR parser (CFG Parsing CFG Problems) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/978-3-662-21545-6.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (implemented on ALGOL) == Year == 1974 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-662-21545-6_18")
- 11:53, 15 February 2023 Papadimitriou and M Yannakakis (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k n)$ == Space Complexity == $O(k)$ auxiliary? words (keep track of maximal matching, and subsequent vertices in cover; note that max size is O(k) else we can reject immediately) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 11:53, 15 February 2023 Earley parser (CFG Parsing CFG Problems) (hist | edit) [526 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1968 == Reference == https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/projec...")
- 11:53, 15 February 2023 Cocke–Younger–Kasami algorithm (CFG Recognition CFG Problems) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * |G|)$ == Space Complexity == $O(n^{2})$ cells (https://core.ac.uk/download/pdf/158319955.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Double-tape TM == Year == 1968 == Reference == https://core.ac.uk/download/pdf/158319955.pdf")
- 11:53, 15 February 2023 Niedermeier, Rossmanith (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.29175}^k k^{2})$. == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1933&rep=rep1&type=pdf")
- 11:53, 15 February 2023 Downey (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.31951}^k k^{2})$ == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.4079&rep=rep1&type=pdf")
- 11:53, 15 February 2023 Valiant (CFG Recognition CFG Problems) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega * |G|)$ where omega is the exponent for matrix multiplication == Space Complexity == $O(n^{2})$? words/cells (See matrix multiplication space complexity) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM and multitape TM == Year == 1975 == Reference == https://linkinghub.elsevier.com/retrieve/pii/S0022000075800468")
- 11:53, 15 February 2023 Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2738}^k+ kn)$ == Space Complexity == $O(poly(n))$ words (https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf")
- 11:53, 15 February 2023 Balasubramanian; Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + ({1.324718})$^k * k^{2}) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.711.8844")
- 11:53, 15 February 2023 J. Chen; L. Liu; and W. Jia. (The Vertex Cover Problem, Degrees Bounded By 3 The Vertex Cover Problem) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k*{1.2192}^k)$ == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/1097-0037(200007)35:4%3C253::AID-NET3%3E3.0.CO;2-K")
- 11:53, 15 February 2023 Chandran and F. Grandoni (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [514 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ == Space Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ but exponential words (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.4409&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://citeseerx.ist.psu.edu/viewdoc/downloa...")
- 11:53, 15 February 2023 Sam Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {2}^k k^{({2}k + {2})})$ == Space Complexity == $O(k^{2})$ auxiliary? words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k^2) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == http://bud.cs.uky.edu/~goldsmit/papers/NondetWithinP.pdf")
- 11:53, 15 February 2023 Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^k n^O({1})$) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:53, 15 February 2023 C-SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See SCAN) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 C-LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See LOOK) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (Needs sorted array of requests and seek distance but not much else) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/scan-elevator-disk-scheduling-algorithms/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 Catriel Beeri Ronald Fagin John H. Howard (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1977 == Reference == https://dl.acm.org/doi/10.1145/509404.509414")
- 11:53, 15 February 2023 SSTF (Disk Scheduling Disk Scheduling) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ with binary tree == Space Complexity == $O(n)$ auxiliary words (https://www.geeksforgeeks.org/program-for-sstf-disk-scheduling-algorithm/?ref=lbp) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 FCFS (Disk Scheduling Disk Scheduling) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Needs to keep track of seek distance but FCFS is fairly straightforward/no extra info needed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 11:53, 15 February 2023 Naive ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference ==")
- 11:53, 15 February 2023 Derek's + Maxwell ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference ==")
- 11:53, 15 February 2023 Räihä; Manilla (Multivalued Dependency Inference Problem Dependency Inference Problem) (hist | edit) [428 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} {2}^n p log p)$ == Space Complexity == $O(n2^n)$? words (bound on size of output (2^n domains, O(n) possible attributes per domain); can probably be improved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315")
- 11:53, 15 February 2023 Maxwell ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference ==")
- 11:53, 15 February 2023 Trino ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
- 11:53, 15 February 2023 Russell et. al. ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==")
- 11:53, 15 February 2023 Brute force algorithm (Functional Dependency Inference Problem Dependency Inference Problem) (hist | edit) [429 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} {2}^n p log p)$ == Space Complexity == $O(n2^n)$? words (bound on size of output (2^n domains, O(n) possible attributes per domain); can probably be improved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://www.sciencedirect.com/science/article/pii/0166218X92900315")
- 11:53, 15 February 2023 Derek's Algorithm ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference ==")
- 11:53, 15 February 2023 Xu; Renio ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference ==")
- 11:53, 15 February 2023 Schlimmer (Functional Dependency Inference Problem Dependency Inference Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n {2}^n p)$ == Space Complexity == $O({2}^n)$ words ((original source, but without user-supplied bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.aaai.org/Papers/Workshops/1993/WS-93-02/WS93-02-017.pdf")
- 11:53, 15 February 2023 Liu (Decisional BCNF BCNF Decomposition) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn^{2})$ == Space Complexity == $O(n)$ words (Derived: Creates an auxiliary database) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://doi.org/10.1016/0950-5849(92)90028-N")
- 11:53, 15 February 2023 Tradu; Mirc ( 4NF Decomposition) (hist | edit) [222 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1967 == Reference ==")
- 11:52, 15 February 2023 Random Split Exponential algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})} * n)$ == Space Complexity == $O({2}^{(n/{2})})$ words (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:52, 15 February 2023 Naive algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [289 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n * n)$ == Space Complexity == $O(n)$ auxiliary words (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:52, 15 February 2023 Hybrid Algorithm (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference ==")
- 11:52, 15 February 2023 String Graph with Ferragina–Manzini Index (Simpson, Durbin) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2881401/pdf/btq217.pdf")
- 11:52, 15 February 2023 String Graph (Myers) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/7497129")
- 11:52, 15 February 2023 De Bruijn Graph (Idury, Waterman) (De Novo Genome Assembly De Novo Genome Assembly) (hist | edit) [383 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires computing O(n) overlaps for graph; data structures are otherwise linear in space usage) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/7497130")
- 11:52, 15 February 2023 Katajainen and M. Koppinen ( Delaunay Triangulation) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://www.semanticscholar.org/paper/Constructing-Delaunay-triangulations-by-merging-in-Katajainen-Koppinen/b13059c096f37407ea680fec0e61e000f6407292")
- 11:52, 15 February 2023 Dwyer (higher dimensions) (General Delaunay Triangulation (d-dimensions) Delaunay Triangulation) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log log n)$ == Space Complexity == $O(n)$? words (Keep track of O(1) information per triangle related to triangulation??) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF02574694")
- 11:52, 15 February 2023 Drysdale; Su (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (See other incremental algorithms) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1996 == Reference == https://web.archive.org/web/20120308043808/http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf")
- 11:52, 15 February 2023 Fortune (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [342 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (See incremental/flipping algorithm space complexities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/142675.142695")
- 11:52, 15 February 2023 S-hull (Sinclair) (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2010 == Reference == http://www.s-hull.org/paper/s_hull.pdf")
- 11:52, 15 February 2023 Dwyer (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840356")
- 11:52, 15 February 2023 Belloch (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [502 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove (see other incremental algos)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2006 == Reference == https://web.archive.org/web/20180425231851/https://www.cs.cmu.edu/~ygu1/pape...")
- 11:52, 15 February 2023 Bowyer–Watson algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [427 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far and which triangles to remove) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1981 == Reference == https://academic.oup.com/comjnl/article/24/2/167/338200")
- 11:52, 15 February 2023 Guibas; Stofli (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Space recursion is S(n)=max(2S(n/2), O(n)) as triangulations from recursive calls are modified in the merge step) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1985 == Reference == http://www.geom.uiuc.edu/~samuelp/del_project.html")
- 11:52, 15 February 2023 Naive algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$? (previously $O(n^{2})$) == Space Complexity == $O(n)$ words (Keep track of triangles in triangulation, and current triangle being tested) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1934 == Reference == -")
- 11:52, 15 February 2023 De Berg; Cheong (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [430 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Keep track of triangles in current triangulation, based on which points have been added so far) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 2008 == Reference == https://web.archive.org/web/20091028054315/http://www.cs.uu.nl/geobook/interpolation.pdf")
- 11:52, 15 February 2023 Flipping algorithm (2-Dimensional Delaunay Triangulation Delaunay Triangulation) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keep track of edges in current triangulation) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1999 == Reference == https://link.springer.com/article/10.1007/PL00009464")
- 11:52, 15 February 2023 9-point FFT (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference ==")
- 11:52, 15 February 2023 5-point cyclic reduction (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")
- 11:52, 15 February 2023 5-point FFT (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 11:52, 15 February 2023 9-point ADI iteration + smooth guess (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference ==")
- 11:52, 15 February 2023 5-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference ==")
- 11:52, 15 February 2023 9-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 11:52, 15 February 2023 9-point SOR iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Need one auxiliary O(n^3)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==")
- 11:52, 15 February 2023 9-point Tensor product (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1964 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0113067")
- 11:52, 15 February 2023 5-point ADI iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} log^{2}n)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference ==")
- 11:52, 15 February 2023 5-point Gauss elimination (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{7})$ == Space Complexity == $O(n^{6})$ words (See Gauss-Jordan elimination, but matrix is of size n^3*n^3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:52, 15 February 2023 5-point Gauss Seidel iteration (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} logn)$ == Space Complexity == $O(n^{3})$? words (Generally uses a constant number of n^3*n^3 matrices where O(n^3) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:52, 15 February 2023 5-point star Cramer's rule (3-Dimensional Poisson Problem Poisson Problem) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({5}^{(n^{3})$}) == Space Complexity == $O({5}^{(n^{3})})$ for sure, $O(n^{3})$ possibly??? (if super conservative) words (For expansion by minors, each "level" of expansion requires computing and storing O(1) smaller determinants, and there are O(n^3) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:42, 15 February 2023 Chin and Poon (LCS Longest Common Subsequence) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(sn + \min\{sp, rm\})$ == Space Complexity == $O(p + n)$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://dl.acm.org/citation.cfm?id=105592")
- 11:42, 15 February 2023 Apostolico and Guerra (Algorithm 2) (LCS Longest Common Subsequence) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(rm + sn + n \log s)$ == Space Complexity == $O(p + sn)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365")
- 11:42, 15 February 2023 Hsu and Du (Scheme 1) (LCS Longest Common Subsequence) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(rm \log(n/m)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254")
- 11:42, 15 February 2023 Hirschberg (LCS Longest Common Subsequence) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(rn + n \log n)$ == Space Complexity == $O(n + p)$ words (https://link.springer.com/content/pdf/10.1007/BF01840365.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=322044")
- 11:42, 15 February 2023 Rick (LCS Longest Common Subsequence) (hist | edit) [379 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(sn + \min\{r(n - r )$, rm\}) == Space Complexity == $O(sn + p)$ words (https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://link.springer.com/chapter/10.1007%2F3-540-60044-2_53")
- 11:42, 15 February 2023 Kuo and Cross (LCS Longest Common Subsequence) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(p + n(r+\log n)$) == Space Complexity == $O(p + n)$ words (https://dl.acm.org/doi/10.1145/74697.74702, Same space complexity as Hunt and Szymanski.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=74702")
- 11:42, 15 February 2023 Apostolico and Guerra (HS1 Algorithm) (LCS Longest Common Subsequence) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m \log n +p \log({2}mn/p)$) == Space Complexity == $O(p + n)$ words (https://link.springer.com/article/10.1007/BF01840365) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840365")
- 11:42, 15 February 2023 Hsu and Du (Scheme 2) (LCS Longest Common Subsequence) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(rm \log(n/r)$ + rm) == Space Complexity == $O(rm)$ words (https://www.sciencedirect.com/science/article/pii/0022000084900254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/0022000084900254")
- 11:42, 15 February 2023 Czumaj (Matrix Chain Scheduling Problem Matrix Chain Multiplication) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{3} n)$ == Space Complexity == $O(n^{2})$? words (Derived: uses two arrays ($D$ and $c$) both of size $O(n^2)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1993 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.9426&rep=rep1&type=pdf")
- 11:42, 15 February 2023 Prakesh Ramanan (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [354 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{4} n)$ == Space Complexity == $O(n)$? words (Derived: $n$ subtrees and each one has a $O(1)$ size trunk) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://epubs.siam.org/doi/abs/10.1137/0225039")
- 11:42, 15 February 2023 Heejo Lee; Jong Kim; Sungje Hong; and Sunggu Lee (Approximate MCSP Matrix Chain Multiplication) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Derived: two $n \times n$ size tables ($S$ and $W$)) == Description == == Approximate? == Approximate Approximation Factor: "near optimal" == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.222&rep=rep1&type=pdf")
- 11:42, 15 February 2023 Spaghetti Sort Parallel Implementation (Non-Comparison Sorting Sorting) (hist | edit) [496 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary? per processor? words (Assuming getting the spaghetti rods doesn't take up any auxiliary space, the only auxiliary space in this algorithm involves the table and the hands, each using O(1) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == ??? == Year == 1984 == Reference == https://link.springer.com/chapter/10.1007...")
- 11:42, 15 February 2023 Odd Even Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) [385 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.semanticscholar.org/paper/Parallel-Neighbor-Sort-(or-the-Glory-of-the-Habermann/bc7b6efb99aae6225239425747fd0169a51f30ce")
- 11:42, 15 February 2023 Probabilistic Convolution Tree (Change-Making Problem Change-Making Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == $O(n log n)$ words (https://pubmed.ncbi.nlm.nih.gov/24626234/) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/24626234")
- 11:42, 15 February 2023 Srba (SLAM Algorithms SLAM Algorithms) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words? (Seems to store a constant number of O(n)*O(n)-sized matrices and O(n)*O(n)-sized tables (see section II, part C)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == http://ingmec.ual.es/~jlblanco/papers/blanco2013rba.pdf")
- 11:42, 15 February 2023 FastSlam (SLAM Algorithms SLAM Algorithms) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log n)$ per iteration == Space Complexity == $O(mn)$? words? (Stores and updates a balanced binary tree of n elements/dimensions per particle) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://robots.stanford.edu/papers/montemerlo.fastslam-tr.pdf")
- 11:42, 15 February 2023 Maximum a Posteriori Occupancy Mapping (Occupancy Grid Mapping Occupancy Grid Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")
- 11:42, 15 February 2023 HEALPix mapping Wong (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference ==")
- 11:42, 15 February 2023 Mauro Steigleder (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:42, 15 February 2023 Emil Praun (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference ==")
- 11:42, 15 February 2023 Heidrich; W.; and H.-P. Seidel (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference ==")
- 11:42, 15 February 2023 Sphere mapping (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference ==")
- 11:42, 15 February 2023 Nate Green (Environment Mapping Texture Mapping) (hist | edit) [252 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference ==")
- 11:42, 15 February 2023 Blinn and Newell (Environment Mapping Texture Mapping) (hist | edit) [243 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == - == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference ==")
- 11:42, 15 February 2023 Bresenham Algorithm (Rasterization Rasterization) (hist | edit) [460 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == Hearn, Baker (1997) pg. 88")
- 11:42, 15 February 2023 Digital Differential Analyzer (DDA) (Rasterization Rasterization) (hist | edit) [492 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ Words (Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.) == Description == "Scan-conversion line algorithm" == Approximate? == Approximate Approximation Factor: n/a == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == Hearn, Ba...")
- 11:42, 15 February 2023 Shani; Brafman; & Shimony; 2005 (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:42, 15 February 2023 Bertsekas & Castanon; 1999; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")
- 11:42, 15 February 2023 McAllester & Singh; 1999; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference ==")
- 11:42, 15 February 2023 Paquet; Tobin; & Chaib-draa; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:42, 15 February 2023 Barto;Bradtke; & Singhe; 1995; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1995 == Reference ==")
- 11:42, 15 February 2023 Washington; 1997; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference ==")
- 11:42, 15 February 2023 Satia & Lave; 1973; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference ==")
- 11:42, 15 February 2023 Spaan & Vlassis; 2005 (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:42, 15 February 2023 Smith & Simmons; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:41, 15 February 2023 Poupart; 2005; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference ==")
- 11:41, 15 February 2023 Braziunas & Boutilier; 2004; (POMDPs POMDPs) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference ==")