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
Help me guys I suck at fractions :(
Nuetrik [128]

Answer:

Answer is D. Please thank me and give 5 stars

3 0
3 years ago
Read 2 more answers
Stephen has a dog that weigths 5 times as much as lan's dog.The total weigths of both dogs is 72 pounds.How much does Stephens d
vesna_86 [32]

Answer: Stephens dog weighs 60 pounds

Step-by-step explanation:

4 0
3 years ago
Mark is in training for a bicycle race. He needs to ride 50 kilometers a week as part of his training. He rode 18.23 kilometers
marishachu [46]

Answer:

17.83 km

Step-by-step explanation:

7 0
3 years ago
If (x+2) is a factor of x^3-6x^2+kx+10, k=
Alja [10]
If a binomial (x-a) is a factor of a polynomial, then a is a root of this polynomial.

(x+2)=(x-(-2)) \Rightarrow a=-2\\\\&#10;(-2)^3-6\cdot(-2)^2+k\cdot(-2)+10=0\\&#10;-8-24-2k+10=0\\&#10;-2k=22\\\&#10;\boxed{k=-11}&#10;

3 0
3 years ago
X * 4 = x + 1.5 = help plzzzzzz!
Leona [35]

Answer:

5

Step-by-step explanation:

x × 4 = x + 15

4x = x + 15

-x -x

3x= 15

-- --

3 3

x = 5

// have a great day //

3 0
3 years ago
Read 2 more answers
Other questions:
  • Cryptomnesia can occur due to source-monitoring error, where __________ plagiarism takes places.
    14·2 answers
  • Which is the area of a circle with diameter 6.4 inches? use 3.14
    15·1 answer
  • Find the sum or difference<br><br> 5+10= ?
    15·2 answers
  • Simple math problem: need help
    8·2 answers
  • What temperature is 24° warmer than-12 °C?
    5·1 answer
  • \/ Question is in attached file \/
    9·2 answers
  • Sam has 33 DVDs all together, the ratio is 2:8:1, there are 3 types.
    7·1 answer
  • In a 24 polygon, 23 of the exterior angles add to 310 degrees. What is the measure of the 24th exterior angle?
    11·1 answer
  • Which choice is equivalent to the quotient below? √100/√25 <br> PLEASE ANSWER I WILL GIVE BRAINLIEST
    13·1 answer
  • A can of soup has a height of 5 in and a diameter of 4 in. Find the area of the label around the soup can.
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!