New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 08:49, 10 April 2023 ‎Kingsford (Motif Search 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")
• 08:49, 10 April 2023 ‎Liang Cwinnower (Motif Search 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")
• 08:49, 10 April 2023 ‎Sagot M (Motif Search Motif Search) (hist | edit) ‎[370 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log(n)$ 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")
• 08:49, 10 April 2023 ‎Bailey TL; Elkan C MEME (Motif Search Motif Search) (hist | edit) ‎[407 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}m^{2})$ == Space Complexity == $O(mn)$ 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")
• 08:49, 10 April 2023 ‎Sinha S; Tompa M YMF (Yeast Motif Finder) (Motif Search 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")
• 08:49, 10 April 2023 ‎Tompa M (Motif Search Motif Search) (hist | edit) ‎[410 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == 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")
• 08:49, 10 April 2023 ‎Van Helden J; Rios AF; Collado-Vides J (Motif Search Motif Search) (hist | edit) ‎[378 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == 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/")
• 08:49, 10 April 2023 ‎Helden Oligo-Analysis (Motif Search Motif Search) (hist | edit) ‎[431 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == 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")
• 08:48, 10 April 2023 ‎B. I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[441 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n)$?? words (Requires computing the coefficients b_i and functions Phi(x) and Psi(x) as in equations 17 and 18) == Description == Discrete Generalized Splines == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == http://sutir.sut.ac.th:8080/sutir/bitstream/123456789/431/1/bib115.pdf")
• 08:48, 10 April 2023 ‎P. Costantini, B. I. Kvasov, and C. Manni (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} \log K)$ == Space Complexity == $O(n)$? words (Derived: Pentadiagonal matrix in the linear system only requires O(n) space) == Description == Pentadiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/article/10.1023/A:1018988312596")
• 08:48, 10 April 2023 ‎V. I. Paasonen (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[229 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5} \log K)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference ==")
• 08:48, 10 April 2023 ‎V. A. Lyul’ka and I. E. Mikhailov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[316 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=943&option_lang=eng")
• 08:48, 10 April 2023 ‎V. A. Lyul’ka and A. V. Romanenko (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[261 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{5})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1994 == Reference == https://www.mathnet.ru/eng/zvmmf2544")
• 08:48, 10 April 2023 ‎B.I. Kvasov (Hyperbolic Spline Interpolation Hyperbolic Spline Interpolation) (hist | edit) ‎[413 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} \log^{2}K)$ == Space Complexity == $O(n)$? words (Derived: Tridiagonal matrices in the linear system only require O(n) space) == Description == Tridiagonal linear system == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1134/S0965542508040039")
• 08:42, 10 April 2023 ‎Knuth–Bendix algorithm (Coset Enumeration Coset Enumeration) (hist | edit) ‎[462 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
• 08:42, 10 April 2023 ‎Haselgrove-Leech-Trotter (HLT) algorithm (Coset Enumeration Coset Enumeration) (hist | edit) ‎[387 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
• 08:42, 10 April 2023 ‎Todd–Coxeter algorithm (Coset Enumeration Coset Enumeration) (hist | edit) ‎[501 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
• 08:36, 10 April 2023 ‎Fortune ( Delaunay Triangulation) (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n)$ words (See Fortune's Algorithm (Voronoi diagrams); Voronoi diagram gives us O(n) circumcenters which can be used to find the O(n) triangles) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1987 == Reference == http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf")
• 08:33, 10 April 2023 ‎Conjugate Gradient (Positive Definite Matrix Linear System) (hist | edit) ‎[409 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(m k^{0.5})$ == Space Complexity == $O(m)$ words (http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1952 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf")
• 08:33, 10 April 2023 ‎Shell Sort (Sedgewick) (Comparison Sorting Sorting) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
• 08:33, 10 April 2023 ‎Shell Sort (Pratt) (Comparison Sorting Sorting) (hist | edit) ‎[312 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log^{2} n)$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
• 08:33, 10 April 2023 ‎Shell Sort (Frank & Lazarus) (Comparison Sorting Sorting) (hist | edit) ‎[313 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
• 08:32, 10 April 2023 ‎Shell Sort (Shell) (Comparison Sorting Sorting) (hist | edit) ‎[311 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
• 08:32, 10 April 2023 ‎Khuller; Matias ( Closest Pair Problem) (hist | edit) ‎[444 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 == Randomized Sieve == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498")
• 08:29, 10 April 2023 ‎Nivasch (Cycle Detection Cycle Detection) (hist | edit) ‎[388 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(\mu + \lambda)$ == Space Complexity == $O(\log\mu)$ Stack size (https://www.gabrielnivasch.org/fun/cycle-detection) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2004 == Reference == https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view")
• 08:29, 10 April 2023 ‎Sedgewick; Szymanski; and Yao (Cycle Detection Cycle Detection) (hist | edit) ‎[400 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ == Space Complexity == M Memory cells (https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat")
• 08:29, 10 April 2023 ‎Eppstein (Subset Sum The Subset-Sum Problem) (hist | edit) ‎[380 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S019667749690841X?via%3Dihub")
• 08:29, 10 April 2023 ‎Compression/Clustering (Vector Quantization) (k-ANNS Nearest Neighbor Search) (hist | edit) ‎[305 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == Varies by codebook structure == Space Complexity == Varies by codebook structure (Table 2) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference ==")
• 08:29, 10 April 2023 ‎Projected radial search (k-ANNS for a dense 3D map of geometric points Nearest Neighbor Search) (hist | edit) ‎[418 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(k)$ == Space Complexity == $O({1})$ words (Derived: There are 5 local variables and no tables or lists aside from input/output) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf")
• 08:29, 10 April 2023 ‎Locality-sensitive hashing (k-ANNS Nearest Neighbor Search) (hist | edit) ‎[474 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time) == Space Complexity == $O(nL)$ hash table cells (https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search) == Description == == Approximate? == Approximate Approximation Factor: c == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf")
• 08:29, 10 April 2023 ‎Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search) (hist | edit) ‎[419 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(M)$ bytes of memory (https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M") == Description == == Approximate? == Approximate Approximation Factor: ? experimental results == Randomized? == No, deterministic == Model of Computation == == Year == 2018 == Reference == https://doi.org/10.1109/TPAMI.2018.2889473")
• 07:57, 10 April 2023 ‎Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[231 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[288 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[250 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[250 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[250 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[367 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) ‎[394 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
• 07:57, 10 April 2023 ‎BOYS algorithm (Entity Resolution Entity Resolution) (hist | edit) ‎[394 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n^{2})$ words (Derived: As written stores counts/probabailities for all pairs of entries.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016794739390116B")
• 07:56, 10 April 2023 ‎Gremban; Miller; Zagha (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) ‎[454 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf) == Description == Support Tree Conjugate Gradients (STCG) == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf")
• 07:55, 10 April 2023 ‎David (Square Matrix LU Decomposition LU Decomposition) (hist | edit) ‎[238 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
• 07:55, 10 April 2023 ‎Closed formula (Square Matrix LU Decomposition LU Decomposition) (hist | edit) ‎[238 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
• 07:54, 10 April 2023 ‎Hirschberg's algorithm (Edit sequence Sequence Alignment) (hist | edit) ‎[329 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://dl.acm.org/doi/10.1145/360825.360861")
• 07:54, 10 April 2023 ‎Masek; Patterson (Edit distance Sequence Alignment) (hist | edit) ‎[382 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
• 07:53, 10 April 2023 ‎No-Steal, Force (hist | edit) ‎[492 bytes] ‎Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal, Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal, No-Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == Currently no algorithms in our database for t...")
• 07:53, 10 April 2023 ‎Steal, No-Force (hist | edit) ‎[914 bytes] ‎Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal, No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal, Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == {| class="wikitable sortable" style="t...")
• 07:53, 10 April 2023 ‎Unweighted Interval Scheduling, Online (hist | edit) ‎[3,094 bytes] ‎Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise...")
• 07:52, 10 April 2023 ‎Root Computation with continuous first derivative (hist | edit) ‎[764 bytes] ‎Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Root Computation with continuous first derivative (Root Computation)}} == Description == Given a real function with continuous first derivative, compute one of the roots. == Related Problems == Related: General Root Computation == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;"...")
• 07:52, 10 April 2023 ‎General Root Computation (hist | edit) ‎[2,713 bytes] ‎Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Related Problems == Related: Root Computation with continuous first derivative == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name...")
• 14:52, 15 February 2023 ‎Reduction from OV to Disjunctive Reachability Queries in MDPs (hist | edit) ‎[563 bytes] ‎Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Reachability Queries in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Symposium...")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)