New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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=")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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...")
- 10: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%...")
- 10: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")
- 10: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")
- 10: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 ==")
- 10: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/...")
- 10: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")
- 10: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...")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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 ==")
- 10: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 ==")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")
- 10: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")