Find link

language:

Find link is a tool written by Edward Betts.

searching for Randomized algorithm 51 found (152 total)

K-server problem (1,290 words) [view diff] exact match in snippet view article find links to article

a randomized algorithm with competitive ratio O(log k) in any arbitrary metric space (with at least k + 1 points). In 2011, a randomized algorithm with

Polygon triangulation (1,386 words) [view diff] exact match in snippet view article find links to article

linear time, though the proposed algorithm is very complex. A simpler randomized algorithm with linear expected time is also known. Seidel's decomposition algorithm

Adversary model (285 words) [view diff] exact match in snippet view article find links to article

Borodin, R. Karp, G. Tardos, A. Wigderson we have: If there is a randomized algorithm that is α-competitive against any adaptive offline adversary then

PostBQP (3,635 words) [view diff] exact match in snippet view article find links to article

PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection) The addition of postselection seems to make

Convex volume approximation (830 words) [view diff] exact match in snippet view article find links to article

and deterministic algorithms. The main result of the paper is a randomized algorithm for finding an ε {\displaystyle \varepsilon } approximation to the

LU decomposition (8,625 words) [view diff] exact match in snippet view article find links to article

to find a low rank approximation to an LU decomposition using a randomized algorithm. Given an input matrix A {\textstyle A} and a desired low rank k

Monotone polygon (1,024 words) [view diff] exact match in snippet view article find links to article

simple polygons in O(n) time with a complex algorithm. A simpler randomized algorithm with linear expected time is also known. Cutting a simple polygon

Median trick (574 words) [view diff] exact match in snippet view article find links to article

regression problems. The idea of median trick is very simple: run the randomized algorithm with numeric output multiple times, and use the median of the obtained

1-vs-2 cycles problem (421 words) [view diff] exact match in snippet view article find links to article

least a logarithmic number of rounds of communication, even for a randomized algorithm that succeeds with high probability (having a polynomially small

Eitan Zemel (1,212 words) [view diff] case mismatch in snippet view article find links to article

Computing. pp. 328–338. Megiddo, N.; E. Zemel (1986). An O(n log n) Randomized Algorithm for the Weighted Euclidean One Center Problem in the Plane. Vol. 7

Search game (585 words) [view diff] exact match in snippet view article find links to article

74–78 (2004). MY Kao, JH Reif and SR Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, SODA 1993.

Word-sense induction (1,010 words) [view diff] exact match in snippet view article find links to article

using the local structural properties of the co-occurrence graph. A randomized algorithm which partitions the graph vertices by iteratively transferring the

Symposium on Theory of Computing (1,162 words) [view diff] exact match in snippet view article find links to article

ISBN 978-1595931344, S2CID 19222958 Russell Impagliazzo (2006), "Can every randomized algorithm be derandomized?", Proceedings of the thirty-eighth annual ACM symposium

Closest pair of points problem (1,215 words) [view diff] exact match in snippet view article find links to article

examples of these algorithm design techniques. A linear expected time randomized algorithm of Rabin (1976), modified slightly by Richard Lipton to make its

Data stream clustering (1,250 words) [view diff] exact match in snippet view article find links to article

algorithm works as follows: Input the first m points; using the randomized algorithm presented in reduce these to ⁠ O ( k ) {\displaystyle O(k)} ⁠ (say

Integer sorting (4,049 words) [view diff] exact match in snippet view article find links to article

to an algorithm with running time O(n log logn K). A complicated randomized algorithm of Han & Thorup (2002) in the word RAM model of computation allows

Alpha–beta pruning (2,405 words) [view diff] exact match in snippet view article find links to article

\Theta ((b/2)^{d})} , which is much smaller than the work done by the randomized algorithm, mentioned above, and is again optimal for such random trees. When

Depth-first search (2,447 words) [view diff] exact match in snippet view article find links to article

Randomized algorithm similar to depth-first search used in generating a maze.

Even–Paz protocol (986 words) [view diff] exact match in snippet view article find links to article

randomized recursive halving algorithm is similar to a well-known randomized algorithm for Ranking - finding the r-ranked element in an array of numbers

Bentley–Ottmann algorithm (3,312 words) [view diff] exact match in snippet view article find links to article

As Clarkson, Cole & Tarjan (1992) show, in this case there is a randomized algorithm for solving the problem in expected time O(n log* n + k), where log*

Selection algorithm (5,755 words) [view diff] exact match in snippet view article find links to article

requires seven comparisons in the worst case, but may be done by a randomized algorithm with an expected number of 6.5 comparisons. More generally, selecting

Unique sink orientation (754 words) [view diff] exact match in snippet view article find links to article

model LP-type problems, it is possible to find the sink using a randomized algorithm in expected time exponential in the square root of d (Gärtner 2002)

Knapsack problem (7,799 words) [view diff] exact match in snippet view article find links to article

and Shamir's Algorithm for Subset Sum, provides as a corollary a randomized algorithm for Knapsack which preserves the O ∗ ( 2 n / 2 ) {\displaystyle O^{*}(2^{n/2})}

Routing (3,766 words) [view diff] exact match in snippet view article find links to article

avoid congestion hot spots in packet systems, a few algorithms use a randomized algorithm—Valiant's paradigm—that routes a path to a randomly picked intermediate

Randomized weighted majority algorithm (2,401 words) [view diff] exact match in snippet view article find links to article

decided before the experts gave their recommendations for the day. The randomized algorithm is better in the worst case than the deterministic algorithm (weighted

Convex hull algorithms (2,326 words) [view diff] exact match in snippet view article find links to article

convex hulls). Chapter 11: Convex Hulls: pp. 235–250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor). The Wikibook

Additive noise differential privacy mechanisms (1,438 words) [view diff] exact match in snippet view article find links to article

this article, M {\displaystyle {\mathcal {M}}} is used to denote a randomized algorithm that releases a sensitive function f {\displaystyle f} under the

Maximally matchable edge (1,268 words) [view diff] exact match in snippet view article find links to article

graphs runs in time O ( V E ) {\displaystyle O(VE)} . There is a randomized algorithm for general graphs in time O ~ ( V 2.376 ) {\displaystyle {\tilde

Light's associativity test (1,321 words) [view diff] exact match in snippet view article find links to article

When X = T, Bednarek's test reduces to Light's test. There is a randomized algorithm by Rajagopalan and Schulman to test associativity in time proportional

Schwartz–Zippel lemma (2,147 words) [view diff] exact match in snippet view article find links to article

\mathbb {N} } , is n {\displaystyle n} a prime number? A simple randomized algorithm developed by Manindra Agrawal and Somenath Biswas can determine probabilistically

Math Girls (1,959 words) [view diff] case mismatch in snippet view article find links to article

(2011-02-26). Sūgaku Gāru: Rantaku Arugorizumu 数学ガール：乱択アルゴリズム [Math Girls: Randomized Algorithm] (in Japanese). Tokyo: SoftBank Creative. ISBN 9784797361001. OCLC 751998119

Robinson–Foulds metric (1,625 words) [view diff] exact match in snippet view article find links to article

only a linear complexity in the number of nodes in the trees. A randomized algorithm that uses hash tables that are not necessarily perfect has been shown

Boolean satisfiability problem (5,045 words) [view diff] exact match in snippet view article find links to article

c-clique if and only if the formula is satisfiable. There is a simple randomized algorithm due to Schöning (1999) that runs in time (4/3)n where n is the number

Michel Raynal (1,499 words) [view diff] exact match in snippet view article find links to article

Byzantine failures. This last algorithm is an incredibly simple randomized algorithm that is optimal with respect to both time and message complexities

Minimum spanning tree (5,460 words) [view diff] exact match in snippet view article find links to article

pairwise comparisons, Karger, Klein & Tarjan (1995) found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete

Shortest path problem (4,764 words) [view diff] case mismatch in snippet view article find links to article

48. Duan, Ran; Mao, Jiayi; Shu, Xinkai; Yin, Longhui (2023). "A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs"

Big O notation (8,735 words) [view diff] case mismatch in snippet view article find links to article

3844–3860. Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons"

Survo puzzle (1,695 words) [view diff] exact match in snippet view article find links to article

Mustonen in April 2006. This program works by using a partially randomized algorithm. The program starts by inserting the missing numbers randomly in

Metric space (11,434 words) [view diff] exact match in snippet view article find links to article

original metric space and converting it into a tree metric via a randomized algorithm. The O ( l o g n ) {\displaystyle O(logn)} distortion bound has led

Zero-knowledge proof (7,668 words) [view diff] exact match in snippet view article find links to article

Probabilistically checkable proof – type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number

SAT solver (3,583 words) [view diff] exact match in snippet view article find links to article

values of k. In the setting with many satisfying assignments the randomized algorithm by Schöning has a better bound. SAT solvers have been used to assist

Travelling salesman problem (11,633 words) [view diff] exact match in snippet view article find links to article

within ( 33 + ε ) / 25 {\displaystyle (33+\varepsilon )/25} by a randomized algorithm. The TSP, in particular the Euclidean variant of the problem, has

Maximum flow problem (5,227 words) [view diff] exact match in snippet view article find links to article

O ( n 2 + o ( 1 ) log ⁡ U ) {\displaystyle O(n^{2+o(1)}\log U)} randomized algorithm when the edge capacities come from the set { 1 , … , U } {\displaystyle

Backpressure routing (7,659 words) [view diff] exact match in snippet view article find links to article

capacity region Λ {\displaystyle \Lambda } , there is a stationary and randomized algorithm that chooses decision variables ( μ a b ∗ ( t ) ) {\displaystyle

Welfare maximization (2,835 words) [view diff] exact match in snippet view article find links to article

approximately with high probability by random sampling. This leads to a randomized algorithm that attains a (1-1/e)-approximation with high probability. In cases

List of eponymous laws (10,530 words) [view diff] exact match in snippet view article find links to article

principle, in computational complexity theory: the expected cost of any randomized algorithm for solving a given problem, on the worst case input for that algorithm

Matroid oracle (4,287 words) [view diff] exact match in snippet view article find links to article

{n}}}\right)} independence queries, much higher than polynomial. Even a randomized algorithm must make nearly as many queries in order to be confident of distinguishing

Egalitarian item allocation (2,969 words) [view diff] exact match in snippet view article find links to article

adaptation of the Adjusted winner procedure. Demko and Hill present a randomized algorithm that attains an egalitarian item allocation in expectation. Below

Maximal independent set (5,451 words) [view diff] exact match in snippet view article find links to article

is in N C 2 {\displaystyle NC_{2}} , they initially presented a randomized algorithm that uses O ( m ) {\displaystyle O(m)} processors but could be derandomized

List of numerical analysis topics (8,335 words) [view diff] exact match in snippet view article find links to article

suitable for processors laid out in a 2d grid Freivalds' algorithm — a randomized algorithm for checking the result of a multiplication Matrix decompositions:

Maximum disjoint set (4,745 words) [view diff] exact match in snippet view article find links to article

{\displaystyle {\frac {n}{u}}\cdot |MDS(C)|} . This is possible either with a randomized algorithm that has a high probability of success and run time O ( n 3 ) {\displaystyle