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
Factor completely 5b^2-11b+6
vekshin1

Answer:

(b - 1) (5b - 6)

Step-by-step explanation:

3 0
3 years ago
Which of the following box and whisker plots correctly displays the data set 120 145 133 105 117 150 ?
blsea [12.9K]

Answer:

3rd answer down

Step-by-step explanation:

ok so you take the median of all the #'s which turns out to be 126.5 and that is where your bar should point to in the box, then you should start with 105, and your last bit of the line should end at 150, the start of your box should start at the median of 105 and 117, and the end of your box should stop at the median of 145 and 150.

7 0
3 years ago
Determine if the following triangle is a right triangle or not using the Pythagorean Theorem Converse. Triangle with side length
seraphim [82]

Answer:

A right triangle is a triangle in which one of the angles is a 90∘ angle. The "square" at the vertex of the angle indicates that it is 90 degrees. A triangle can be determined to be a right triangle if the side lengths are known.

6 0
3 years ago
Describe how the placement of the decimal point changes when you multiply a number by the power of ten. How is this the same and
Solnce55 [7]

Answer: the answer to your question is

Recall that when you multiply a decimal by a power of ten (10, 100, 1,000, etc), the placement of the decimal point in the product will move to the right according to the number of zeros in the power of ten. For instance, 4.12 · 10 = 41.2.

hope this helps for what you needed have a nice day! :)

3 0
3 years ago
1/3×(9x + 3) = 3x = - 1 3​
balu736 [363]

Answer:

1/3* (9x-6) = 2x+3

⇒ (1/3)(9x)- (1/3)*6 = 2x+3 (distributive property)

⇒ 3x - 2= 2x + 3

⇒ (3x-2x) -2 = (2x-2x) +3

⇒ x-2=3

⇒ x +(-2+2) = 3+2

⇒ x= 5.

Step-by-step explanation:

pls i beg u pls mark me as a brainlliest

3 0
3 years ago
Other questions:
  • What is the height of a solid with a volume of 120m and base area of 30m
    9·1 answer
  • No one seems to be he;ping with this question so please help and show proof of how u got the answer
    6·1 answer
  • Math help @Alessandroarenas
    5·1 answer
  • Calculate the m angle CLA , given m arc AC = 160° and m arc AKC = 200°.
    7·2 answers
  • Pls2sssssssssssssssssssssss
    13·1 answer
  • The small rectangle was enlarged to create the big rectangle. A smaller rectangle has a length of 12 feet and a width of 2 feet.
    10·2 answers
  • 1) Venn-diagram of-<br> AUBUC={a,b,c,d,e}U{d,e,f,g,h,i}U{a,e,i,o,u}<br>​
    5·1 answer
  • The lieutenant noted that 0.68 of the frontiersmen at the conclave wore buckskin. If 512 did not wear buckskin, how many frontie
    7·2 answers
  • Determine the initial value
    10·1 answer
  • Simplify<br> b^10/b^2<br><br> OA. b^-8<br> OB. b^5 <br> O c. b^-5<br> O D. b^8
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!