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
Jake is using a horse trailer to take his horses to his new ranch. 1 Horse= 1,200 lb Trailer= 2,700 lb Jake's truck can tow a ma
Kitty [74]

Answer:

Jack can take only 1 horse on his trailer to be towed by the truck without going over the maximum weight the truck.

Step-by-step explanation:

Given:

Weight of 1 horse = 1,200 lb

Weight of trailer = 2,700 lb

Jacks'truck can tow a maximum of 5000 pounds.

To find the maximum number of horses Jack can take in his trailer without going over the maximum weight his truck can tow.

Solution:

Let the maximum number of horses that Jack can take be = x

Using unitary method to find weight of x horses.

If 1 horse weights = 1,200 lb

Then x horses will weight in lbs = 1,200\times x = 1,200x

Total weight of horses and trailer in lbs = 1200x+2700

Since the maximum weight the truck can tow = 5,000 lb, so the inequality can be given as:

1200x+2700\leq5000

Subtracting both sides by 2700.

1200x+2700-2700\leq5000-2700

1200x\leq2300

Dividing both sides by 1200.

\frac{1200x}{1200}\leq\frac{2300}{1200}

x\leq1.91

From the inequality solution for x, we can conclude that Jack can take only 1 horse on his trailer to be towed by the truck without going over the maximum weight the truck.

3 0
3 years ago
Farmer Emmet used to own 2,300 acres of farmland. However, he recently sold 28% of his farm to a residential developer.
kap26 [50]

9514 1404 393

Answer:

  1. 1656 acres left
  2. 644 acres sold
  3. $32,200,000

Step-by-step explanation:

1. The number of acres sold is ...

  28% × 2300 = 0.28 × 2300 = 644

Then the number of acres Emmet has left will be ...

  2300 -644 = 1656 . . . acres left

__

2. Emmet sold 644 acres.

__

3. At $50,000 per acre, the value of the land sold was ...

  $50,000 × 644 = $32,200,000 . . . . paid by the developer

5 0
2 years ago
Use the information in the picture.
Katarina [22]
Yes, parallelogram congruent angles theorem
8 0
3 years ago
PLEASE NO LINKS.
Kamila [148]

Answer:

Step-by-step explanation:

Sustituye la variable  

y

con  

|

x

−

3

|

+

|

x

+

2

|

−

|

x

−

5

|

en la expresión.

s

i

−

2

3 0
2 years ago
Cecil had 6 ice cubes. He put 1 ice cube in each glass. In how many glasses did Cecil put ice cubes?
Kamila [148]
He only puts 1 in each glass and he has six. The answer is 6.
7 0
2 years ago
Read 2 more answers
Other questions:
  • Given that there are 28.3495 grams in an ounce, find the number of ounces in the heaviest item listed above.
    15·1 answer
  • Samples of size n = 125 are randomly selected from the U.S. census data, and the median children per household is found for each
    11·2 answers
  • Translate this sentence into an equation.
    13·1 answer
  • The height of a tree in feet over x years is modeled by the function f(x).
    8·2 answers
  • Can an object with constant acceleration reverse its direction? explain​
    5·1 answer
  • I am not sure on this question can someone please explain and solve for me ASAP
    10·1 answer
  • Which terms are properties of mathematical proofs?
    15·1 answer
  • Each face of a cube has an area of 400 cm2. what is the volume of the cube?
    14·1 answer
  • Answer all please number 2
    6·1 answer
  • Write the verbal sentence as an equation. Then solve.
    5·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!