Find link

Randomized algorithm not in Depth-first search

language:

Find link is a tool written by Edward Betts.

searching for Randomized algorithm 50 found (153 total)

K-server problem (1,383 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,629 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 (852 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

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,220 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

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

Integer sorting (4,057 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

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

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

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

Depth-first search (2,446 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.

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

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*

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)

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

Knapsack problem (7,745 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})}

Alpha–beta pruning (2,408 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

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

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.

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,262 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

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

Boolean satisfiability problem (4,820 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

Schwartz–Zippel lemma (2,269 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

Minimum spanning tree (5,458 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,868 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"

Claw-free graph (3,989 words) [view diff] exact match in snippet view article find links to article

that claw-free graphs can be recognized with high probability by a randomized algorithm running in the matrix multiplication O ~ ( n 2.372 ) {\displaystyle

Big O notation (9,101 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"

Metric space (11,435 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

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

Simulation (13,234 words) [view diff] exact match in snippet view article find links to article

Technology used for training miners Monte Carlo algorithm – Type of randomized algorithm Network simulation – Simulating computer networks Pharmacokinetics

SAT solver (3,632 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

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

scheme Probabilistically checkable proof – Proof checkable by a randomized algorithm Proof of knowledge – Class of interactive proof Topics in cryptography

Welfare maximization (2,831 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

Travelling salesman problem (11,590 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 (6,012 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

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,988 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,460 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,327 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,743 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