User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 11:1811:18, 15 February 2023 diff hist +340 N Lipton, Markakis and Mehta method (2 player games Nash Equilibria) Created page with "== Time Complexity == $O(n^{c log n/eps^2})$ == Space Complexity == $O(log^{2} n/eps^{2})$ words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM words == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933" current
- 11:1811:18, 15 February 2023 diff hist +292 N Treap ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf" current
- 11:1811:18, 15 February 2023 diff hist +396 N Blum, Shelton, Koller (Graphical games, Multi-agent influence diagrams Nash Equilibria) Created page with "== Time Complexity == Unknown? == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2003 == Reference == https://www.semanticscholar.org/paper/A-Continuation-Method-for-Nash-Equilibria-in-Games-Blum-Shelton/4a3b80041922298db147debc2a2307bc4a5a42e9" current
- 11:1811:18, 15 February 2023 diff hist +303 N Tango Tree ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O((k+{1})$log(log(n))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf" current
- 11:1811:18, 15 February 2023 diff hist +335 N Lemke-Howson Algorithm (2 player games Nash Equilibria) Created page with "== Time Complexity == Exponential == Space Complexity == $O(mn)$? words (I am not sure if this can be optimized?) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1964 == Reference == https://doi.org/10.1137/0112033" current
- 11:1811:18, 15 February 2023 diff hist +322 N Scapegoat Tree ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859" current
- 11:1811:18, 15 February 2023 diff hist +264 N Bayer, McCreight B-Tree ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +249 N Tarjan Splay Tree ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +292 N Treap ( Self-Balancing Trees Deletion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf" current
- 11:1811:18, 15 February 2023 diff hist +353 N AVL Tree ( Self-Balancing Trees Search) Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Need to keep track of constant amount of info during search (i.e. which node we're on and what direction to go)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +318 N Scapegoat Tree ( Self-Balancing Trees Deletion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859" current
- 11:1811:18, 15 February 2023 diff hist +299 N Bayer, McCreight B-Tree ( Self-Balancing Trees Deletion) Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +249 N Tarjan Splay Tree ( Self-Balancing Trees Deletion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +292 N Treap ( Self-Balancing Trees Insertion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf" current
- 11:1811:18, 15 February 2023 diff hist +252 N AVL Tree ( Self-Balancing Trees Deletion) Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +318 N Scapegoat Tree ( Self-Balancing Trees Insertion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859" current
- 11:1811:18, 15 February 2023 diff hist +299 N Bayer, McCreight B-Tree ( Self-Balancing Trees Insertion) Created page with "== Time Complexity == $O(b*log(n)$/log(b))? == Space Complexity == $O(b)$? words (^see above, but with branching factor involved) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +249 N Tarjan Splay Tree ( Self-Balancing Trees Insertion) Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +359 N AVL Tree ( Self-Balancing Trees Insertion) Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ words (Each node being changed requires constant auxiliary space to make changes; can reuse space across nodes being changed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +363 N Tango Tree ( Self-Balancing Trees Creation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf" current
- 11:1811:18, 15 February 2023 diff hist +376 N Scapegoat Tree ( Self-Balancing Trees Creation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.4859" current
- 11:1811:18, 15 February 2023 diff hist +350 N Treap ( Self-Balancing Trees Creation) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Need to keep track of intermediary stages of tree before outputting) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1989 == Reference == http://faculty.washington.edu/aragon/pubs/rst89.pdf" current
- 11:1811:18, 15 February 2023 diff hist +356 N Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem) Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + $O({1})$}) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018" current
- 11:1811:18, 15 February 2023 diff hist +353 N Babai 1980 (Graph Isomporhism, Trivalent Graphs Graph Isomorphism Problem) Created page with "== Time Complexity == \exp(cn^{\frac{1}{2}} \log n) == Space Complexity == $O(n^{2})$ words (https://epubs.siam.org/doi/epdf/10.1137/0209018) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018" current
- 11:1811:18, 15 February 2023 diff hist +315 N Gronlund, Pettie (3-Clique Exact-Weight k-Clique Problem) Created page with "== Time Complexity == $O(n^{3}*(log log n)$^{2}/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047" current
- 11:1811:18, 15 February 2023 diff hist +298 N Brute force enumeration (k-Clique k-Clique Problem) Created page with "== Time Complexity == $O(n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vertices we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
- 11:1811:18, 15 February 2023 diff hist +440 N Nesetril, Poljak (k-Clique k-Clique Problem) Created page with "== Time Complexity == $O(n^(k-({3}-\omega)*floor(k/{3}))$ where omega is the exponent on matrix multiplication == Space Complexity == $O(n^({2}k/{3})$) ish words (matrix sizes) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://dml.cz/bitstream/handle/10338.dmlcz/106381/CommentatMathUnivCarol_026-1985-2_22.pdf" current
- 11:1811:18, 15 February 2023 diff hist +256 N APSP algorithm (3-Clique Min-Weight k-Clique Problem) Created page with "== Time Complexity == $O(n^{3} / {2}^(log n)$^{0.5}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
- 11:1811:18, 15 February 2023 diff hist +315 N Reduction to Chan, Williams (k-OV Orthogonal Vectors) Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87" current
- 11:1811:18, 15 February 2023 diff hist +317 N Chan, Williams (OV Orthogonal Vectors) Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch87" current
- 11:1811:18, 15 February 2023 diff hist +314 N Abboud, Williams, Yu (OV Orthogonal Vectors) Created page with "== Time Complexity == $O(n^{({2}-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17" current
- 11:1811:18, 15 February 2023 diff hist +312 N Reduction to Abboud, Williams, Yu (k-OV Orthogonal Vectors) Created page with "== Time Complexity == $O(n^{(k-{1}/O(d/log(n)))})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.17" current
- 11:1811:18, 15 February 2023 diff hist +337 N Exhaustive search (Minimum Wiener Connector problem Wiener Index) Created page with "== Time Complexity == {2}^($O(n)$) == Space Complexity == $O(n)$ auxiliary words (Keeps track of current subset being checked, minimum subset, and O(1) Wiener indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference ==" current
- 11:1811:18, 15 February 2023 diff hist +299 N Exhaustive search (k-OV Orthogonal Vectors) Created page with "== Time Complexity == $O(d*n^k)$ == Space Complexity == $O(k)$ auxiliary words (keeping track of which vectors we're looking at) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -" current
- 11:1811:18, 15 February 2023 diff hist +309 N Wen (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016781919400063G" current
- 11:1811:18, 15 February 2023 diff hist +322 N KALYAN PERUMALLA and NARSINGH DEO (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.1291&rep=rep1&type=pdf" current
- 11:1811:18, 15 February 2023 diff hist −17 Smith (2-dimensional Maximum subarray problem) No edit summary Tag: Reverted
- 11:1811:18, 15 February 2023 diff hist +350 N Takaoka (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S1571066104003135?via%3Dihub" current
- 11:1811:18, 15 February 2023 diff hist +357 N Tamaki, Tokuyama (approximate) (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^(omega)$ * (-log(epsilon))/epsilon) == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: (1-epsilon) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823" current
- 11:1811:18, 15 February 2023 diff hist +320 N Tamaki, Tokuyama (exact) (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^{3} * ((log log n)$/(log n))^({1}/{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://dl.acm.org/doi/pdf/10.5555/314613.314823" current
- 11:1811:18, 15 February 2023 diff hist +343 N Smith (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(log n)$ auxiliary? words (divide-and-conquer) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0167642387900347"
- 11:1811:18, 15 February 2023 diff hist +331 N Brute force (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^{6})$ == 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 RAM == Year == 1977 == Reference == -" current
- 11:1811:18, 15 February 2023 diff hist +374 N Bentley (2-dimensional Maximum subarray problem) Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ auxiliary? words ((i think you need to pre-process to get cumulative sums in each row?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/pdf/10.1145/1968.381154" current
- 11:1811:18, 15 February 2023 diff hist +371 N Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) Created page with "== Time Complexity == $O(kn+({1.2906})$^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://mediatum.ub.tum.de/doc/1094228/file.pdf" current
- 11:1811:18, 15 February 2023 diff hist +442 N Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) Created page with "== Time Complexity == $O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k 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 == 1999 == Reference == https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/69332/eth-4359-01.pdf" current
- 11:1811:18, 15 February 2023 diff hist +453 N Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) Created page with "== Time Complexity == $O({3}^k k^{2}+kn)$ == 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) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586" current
- 11:1811:18, 15 February 2023 diff hist +467 N Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) Created page with "== Time Complexity == $O(kn+{2}^k 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) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.7270&rep=rep1&type=pdf" current
- 11:1811:18, 15 February 2023 diff hist +315 N Chan (Real 3SUM 3SUM) Created page with "== Time Complexity == $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2018 == Reference == https://dl.acm.org/doi/abs/10.1145/3363541" current
- 11:1811:18, 15 February 2023 diff hist +343 N Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) Created page with "== Time Complexity == $O(C(n, k)$) (i.e. (n, k) binomial coefficient) == 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 ==" current
- 11:1811:18, 15 February 2023 diff hist +317 N Freund (Real 3SUM 3SUM) Created page with "== Time Complexity == $O(n^{2}*(log log n)$/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://link.springer.com/article/10.1007/s00453-015-0079-6" current