New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:35, 15 February 2023 Bitap algorithm (Single String Search String Search) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses a bit array of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://en.wikipedia.org/wiki/Bitap_algorithm")
- 10:35, 15 February 2023 Bunch; Hopcroft (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{37}6})$ == Space Complexity == $\tilde{O}(n^{2})$ words (Derived: Uses Strassen multiplication and a constant number of $n \times n$ auxiliary matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/citation.cfm?id=248979")
- 10:35, 15 February 2023 Khuller; Matias Randomized Sieve ( Closest Pair Problem) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$, not sure if this is auxiliary not mentioned (https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://dl.acm.org/citation.cfm?id=207181")
- 10:35, 15 February 2023 Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring) (hist | edit) [654 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7272}^n)$ == Space Complexity == $O(n)$ words (Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity) == Description == == Approximate? == Exac...")
- 10:35, 15 February 2023 Petford and Welsh (3-Graph Coloring Graph Coloring) (hist | edit) [465 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: we store the coloring of each vertex in a dictionary and the maximum size of this dictionary is equal to the number of vertices in the graph, n.) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0012365X89902148")
- 10:35, 15 February 2023 Rao-Blackwellized Particle Filtering SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words? ((based on Section 4 of the paper?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://papers.nips.cc/paper/1716-bayesian-map-learning-in-dynamic-environments.pdf")
- 10:35, 15 February 2023 Compressed Extended KF (SLAM Algorithms SLAM Algorithms) (hist | edit) [421 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.999&rep=rep1&type=pdf")
- 10:35, 15 February 2023 UKF (SLAM Algorithms SLAM Algorithms) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://www.seas.harvard.edu/courses/cs281/papers/unscented.pdf")
- 10:35, 15 February 2023 EKF SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) [417 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == http://ais.informatik.uni-freiburg.de/teaching/ss12/robotics/slides/12-slam.pdf")
- 10:35, 15 February 2023 Image quilting Efros-Freeman (Texture Synthesis Texture Synthesis) (hist | edit) [303 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 == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383296")
- 10:35, 15 February 2023 R. Paget ; I.D. Longstaff (Texture Synthesis Texture Synthesis) (hist | edit) [307 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 == https://ieeexplore.ieee.org/abstract/document/679446")
- 10:35, 15 February 2023 Image analogies Hertzmann (Texture Synthesis Texture Synthesis) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N log n)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/abs/10.1145/383259.383295")
- 10:35, 15 February 2023 Non-parametric sampling Efros and Leung (Texture Synthesis Texture Synthesis) (hist | edit) [307 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 == 1999 == Reference == https://ieeexplore.ieee.org/abstract/document/790383")
- 10:35, 15 February 2023 Petro Vlahos Algorithm (Image Compositing Image Compositing) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k/r)$ == Space Complexity == $O(nk)$?? words (Keeps track of all pixels across all images) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1985 == Reference ==")
- 10:35, 15 February 2023 Roth AlignACE (Motif Search Motif Search) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: essentially just modified Gibbs sampling) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9788350")
- 10:35, 15 February 2023 Alon; Moshkovitz & Safra (Unweighted Set-Covering The Set-Covering Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/doi/pdf/10.1145/1150334.1150336")
- 10:35, 15 February 2023 Chvatal greedy heuristic (Weighted Set-Covering The Set-Covering Problem) (hist | edit) [455 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn^{2})$ == Space Complexity == $O(dm)$ (Derived -- worst case, updating each set in S to be something else and we don't want to change the input) == Description == == Approximate? == Approximate Approximation Factor: ln n - lnln n + \Theta(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1979 == Reference == https://www.jstor.org/stable/3689577#metadata_info_tab_contents")
- 10:35, 15 February 2023 The SUSAN corner detector ( Corner Detection) (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 == 1997 == Reference ==")
- 10:35, 15 February 2023 L. Kitchen and A. Rosenfeld (Grey-scale Corner Detection) (hist | edit) [325 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 == 1982 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0167865582900204")
- 10:34, 15 February 2023 Harris and Stephens algorithm ( Corner Detection) (hist | edit) [299 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 == 1988 == Reference == http://www.bmva.org/bmvc/1988/avc-88-023.pdf")
- 10:34, 15 February 2023 Barvinok (Geometric Maximum TSP The Traveling-Salesman Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} loglogE)$ == Space Complexity == $O(V)$? memory cells (Derived: One memory cell per tunnel-city pair, with one tunnel total) == Description == Tunneling == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/876638.876640")
- 10:34, 15 February 2023 Dantzig-Fulkerson-Johnson (DFJ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == $O({2}^V)$ words (http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1954 == Reference == https://doi.org/10.1287/opre.2.4.393")
- 10:34, 15 February 2023 Miller-Tucker-Zemlin (MTZ) formulation (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $exp(V)$ == Space Complexity == $O(V^{4})$ words (Derived: V^2 + 2V constraints on V^2 variables, most integer programs use space of O(nm) where n=#vars and m=#constraints) == Description == ILP formulation == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/doi/10.1145/321043.321046")
- 10:34, 15 February 2023 Micali and Vazirani ( Maximum Cardinality Matching) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(V)$ not mentioned (https://link.springer.com/content/pdf/10.1007/PL00009186.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Restricted Randomness (RR) == Year == 1980 == Reference == https://dl.acm.org/doi/10.1109/SFCS.1980.12")
- 10:34, 15 February 2023 Brélaz (DSatur) (3-Graph Coloring Graph Coloring) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V + E)$ words (Derived using adjacency lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://dl.acm.org/doi/10.1145/359094.359101")
- 10:34, 15 February 2023 Karger, Blum ( Graph Coloring) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(poly(V))$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: $\tilde{O}(n^{3/14})$ == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4204")
- 10:34, 15 February 2023 Schonhage's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{({3}*log52/log110)}) ~ O(n^{2.{521}8})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/abs/10.1137/0210032")
- 10:34, 15 February 2023 Bini's algorithm (Matrix Multiplication Matrix Product) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{779}9})$ == Space Complexity == $O(n^{2})$ words (Derived: Same idea as Strassen's, plus three additional nxn matrices) == Description == == Approximate? == Approximate Approximation Factor: $O(n logn)$ error == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://doi.org/10.1016/0020-0190(79)90113-3")
- 10:34, 15 February 2023 Chin (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: There are a few auxiliary variables, only one of which is variable length. That is a list of length $O(n)$.) == Description == == Approximate? == Approximate Approximation Factor: 1.2485 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://dl.acm.org/citation.cfm?id=359556")
- 10:34, 15 February 2023 Chandra (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [502 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: cannot find pdf of original paper or any description of the actual algorithm, but likely the same space as Chin's algorithm) == Description == == Approximate? == Approximate Approximation Factor: 2 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.worldcat.org/title/computing-matrix-chain-products-in-near-...")
- 10:34, 15 February 2023 Czumaj (Approximate MCOP Matrix Chain Multiplication) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\log n)$ == Space Complexity == $O(n)$ words? (Derived: solving the optimal triangulation problem of a convex polygon where there are $n+1$ vertices and $n+1$, so total $O(n)$ auxiliary space) == Description == == Approximate? == Approximate Approximation Factor: 1.1547 == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?d...")
- 10:34, 15 February 2023 Dynamic Programming (Change-Making Problem Change-Making Problem) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Sn)$ == Space Complexity == $O(Sn)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == https://dl.acm.org/doi/10.1145/321864.321874")
- 10:34, 15 February 2023 Brute Force (Change-Making Problem Change-Making Problem) (hist | edit) [258 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(S^n)$ == Space Complexity == $O(n)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == NA")
- 10:34, 15 February 2023 Dynamic Programming (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [255 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference ==")
- 10:34, 15 February 2023 Brute Force (Rod-Cutting Problem Rod-Cutting Problem) (hist | edit) [257 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 10:34, 15 February 2023 PMS (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm^{2} \sigma)$ == Space Complexity == $O(m^{2} n)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://ieeexplore.ieee.org/abstract/document/4359890")
- 10:34, 15 February 2023 Risotto (Motif Search Motif Search) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2})$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11682462_69")
- 10:34, 15 February 2023 Census (Motif Search Motif Search) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45078-8_5")
- 10:34, 15 February 2023 Mitra (Motif Search Motif Search) (hist | edit) [372 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k nm \sigma)$ == Space Complexity == $O(mnk)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://pubmed.ncbi.nlm.nih.gov/12169566/")
- 10:34, 15 February 2023 Speller (Motif Search Motif Search) (hist | edit) [390 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2} \sigma)$ == Space Complexity == $O(mn^{2}/w)$ words (https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2966288/pdf/1471-2105-11-S8-S1.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0054337")
- 10:34, 15 February 2023 Perumalla and Deo (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ auxiliary words (constant number of arrays as outlined in algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf")
- 10:34, 15 February 2023 Kadane's Algorithm (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [301 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (keep track of current tail sum and best sum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1982 == Reference == -")
- 10:34, 15 February 2023 Shamos (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [290 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(log n)$ auxiliary words (keep track of recursive maximums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == -")
- 10:34, 15 February 2023 Faster Brute Force (via x(L:U) = x(L:U-1)+x(U)) (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://dl.acm.org/doi/pdf/10.1145/358234.381162")
- 10:34, 15 February 2023 Grenander (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (storing precomputed cumulative sums) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Brute Force (1D Maximum Subarray Maximum Subarray Problem) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (keep track of which subarray is being computed, along with current maximum) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == -")
- 10:34, 15 February 2023 Bringman (Subset Sum The Subset-Sum Problem) (hist | edit) [395 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(nt^{1+\epsilon})$ == Space Complexity == \tilde{O}(nt^\epsilon) (https://arxiv.org/abs/1610.04712) == Description == == Approximate? == Approximate Approximation Factor: (n+t)^{-\Omega(1)} error == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1610.04712")
- 10:34, 15 February 2023 Koiliaris and Xu (Subset Sum The Subset-Sum Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2019 == Reference == https://dl.acm.org/doi/pdf/10.1145/3329863")
- 10:34, 15 February 2023 Psinger (Subset Sum The Subset-Sum Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n max(S))$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0196677499910349")
- 10:34, 15 February 2023 Bellman dynamic programming algorithm (Subset Sum The Subset-Sum Problem) (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1956 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/nav.3800030107")