1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nana76 [90]
3 years ago
11

• karger's min cut algorithm in the class has probability at least 2/n2 of returning a min-cut. how many times do you have to re

run this algorithm to get the probability of an error to be at most 1/n?
Mathematics
1 answer:
MrRissso [65]3 years ago
4 0
The Karger's algorithm relates to graph theory where G=(V,E)  is an undirected graph with |E| edges and |V| vertices.  The objective is to find the minimum number of cuts in edges in order to separate G into two disjoint graphs.  The algorithm is randomized and will, in some cases, give the minimum number of cuts.  The more number of trials, the higher probability that the minimum number of cuts will be obtained.

The Karger's algorithm will succeed in finding the minimum cut if every edge contraction does not involve any of the edge set C of the minimum cut.

The probability of success, i.e. obtaining the minimum cut, can be shown to be ≥ 2/(n(n-1))=1/C(n,2),  which roughly equals 2/n^2 given in the question.Given: EACH randomized trial using the Karger's algorithm has a success rate of P(success,1) ≥ 2/n^2.

This means that the probability of failure is P(F,1) ≤ (1-2/n^2) for each single trial.

We need to estimate the number of trials, t, such that the probability that all t trials fail is less than 1/n.

Using the multiplication rule in probability theory, this can be expressed as
P(F,t)= (1-2/n^2)^t < 1/n 

We will use a tool derived from calculus that 
Lim (1-1/x)^x as x->infinity = 1/e, and
(1-1/x)^x < 1/e   for x finite.  

Setting t=(1/2)n^2 trials, we have
P(F,n^2) = (1-2/n^2)^((1/2)n^2) < 1/e

Finally, if we set t=(1/2)n^2*log(n), [log(n) is log_e(n)]

P(F,(1/2)n^2*log(n))
= (P(F,(1/2)n^2))^log(n) 
< (1/e)^log(n)
= 1/(e^log(n))
= 1/n

Therefore, the minimum number of trials, t, such that P(F,t)< 1/n is t=(1/2)(n^2)*log(n)    [note: log(n) is natural log]
You might be interested in
Three to the fourth power.<br> Write the numerical answer only.
irakobra [83]
30000 is the answer I think
8 0
3 years ago
Four less than twice the square of x is 124. Which equation can be used to find the value of x?
tester [92]
2x^2-4=124 is the correct answer.
5 0
3 years ago
a rabbit can run 35 miles per hour. a fox run can run 21 miles in half an hour.which animal is faster,and by how much
lord [1]

Answer:

the rabbit by 14 miles per hour

Step-by-step explanation:

The rabbit because if you subtract 35 from 21 it gives you 14

6 0
3 years ago
Read 2 more answers
Which vertex will result in the minimum value of the function T = x - 2y?
PilotLPTM [1.2K]

Answer:

the objective function, P, at each vertex ... Example: Find the maximum and minimum values of P=3x+2y subject to x + 4y ≤ 20 ... We can find the intersection of the two lines.

6 0
3 years ago
The equation y=19x relates proportional quantities x and y. What is the value of x when y is 4? Enter your answer in the box
Igoryamba

\frac{4}{19}

8 0
3 years ago
Read 2 more answers
Other questions:
  • he wanted to make another quilt with an area of 42 square feet what are its possible dimensions if they must be whole numbers. W
    11·1 answer
  • Area of a pentagon with a radius of 8m
    14·1 answer
  • Currency is used to ?
    5·1 answer
  • Calcule o valor de x, sabendo que as retas “e” “f” e “a” são paralelas
    13·1 answer
  • What is the opposite of -2​
    6·2 answers
  • A baker has 3 eggs to use for making cakes. Each cake takes 5 eggs.
    6·1 answer
  • PLEASE HELP IM LITERALLY STUCK!
    5·1 answer
  • Which equation represents a line which is parallel
    11·1 answer
  • The marked price of a textbook is $20. A school is given a 6.5% discount. Find the amount of money the
    13·2 answers
  • The Juice Cafe posted the sign below showing the prices of smoothies of various sizes.
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!