Decision Making and Optimization

Randomized Algorithms

Randomized Algorithms 1 / 29
 Decision Making and Optimization

Introduction

• In this lecture we discuss some randomized algorithms to tackle

well-known optimization problems.
• What does a randomized algorithm mean? it is simply an algorithm
that considers random choices along its steps.
• Questions: how can we evaluate the performance of an algorithm that
plays random? Is that a good algorithm or not? What is the expected
performance? Are there instances where the algorithm performs very
badly?...

Randomized Algorithms 2 / 29
 Decision Making and Optimization

Introduction

• Difficult questions in general...

• We will see beautiful arguments to successfully answer these
questions.
• Randomized algorithms may perform better than known deterministic
algorithms and often they are more elegant and simpler.
• We will consider the following optimization problems:
Min-cut, k-SAT.
• Note: the contents of this lecture are largely inspired to Chapter 10 of
the book: C. Moore, S. Mertens. The Nature of Computation, 2011.

Randomized Algorithms 3 / 29
 Decision Making and Optimization

The importance of being...random

• In adversarial games and real-life situations the best strategy to play
often involves random decisions (e.g. games such as Rock, Paper,
Scissors).
• Why? to fool an adversary who could carefully study your
deterministic strategies and beat you.
• In game theory, many Nash equilibria are given by mixed strategies
(namely where each player chooses his/her strategy according to
some probability distributions).
• In our context, we consider the following game:
1 You want to design an algorithm for solving a given problem.
2 An adversary chooses an instance of the problem and you have to solve
the instance by your algorithm.
3 The goal of your adversary is to select a proper instance on which your
algorithm performs as bad as possible (in terms of running time).
• Assume that your adversary is very smart...
Randomized Algorithms 4 / 29
 Decision Making and Optimization

The importance of being...random

• ...if you decide to develop a deterministic algorithm, you will make the
life of your adversary very easy:
• He/she can carefully study the steps of your algorithm and construct
a very bad instance!
• But if your algorithm makes random moves, the adversary cannot
exactly predict the behavior of your algorithm, no matter how smart
he/she is.
• So the adversary cannot build up a hard instance in advance.
• Still, you would like to have an algorithm that performs good on
average.
• What does the word “average” mean here?

Randomized Algorithms 5 / 29
 Decision Making and Optimization

The importance of being...random

• On the one hand, “average” could refer to the fact that the algorithm
is deterministic and the instance is random. So we average over all
possible instances to derive an average performance of the algorithm.
• Example: Quicksort algorithm has an average running time of
Θ(n log n) (roughly speaking f (n) = Θ(g (n)) means “f = g ”).
• This meaning of the word “average” does not make sense in our
game:
The adversary chooses the instance. Thus he/she can just come up
with a worst-case instance for Quicksort increasing the running time
to Θ(n2 ).

Randomized Algorithms 6 / 29
 Decision Making and Optimization

The importance of being...random

• On the other hand, “average” could mean that your adversary selects
the instance and the algorithm is randomized.
• In this case we average over all possible random sequences of moves
that the algorithm can take.
• With random choices you may obtain a guarantee on the average
performance of your algorithm even when worst-case instances are
considered.
• Clearly if your algorithm makes a series of bad random moves, it
could still perform with the worst-case running time...
• ...but this behavior would be due to a bad luck only and would not be
due to the adversary skills.

Randomized Algorithms 7 / 29
 Decision Making and Optimization

The importance of being...random

• In other words, randomization can “spread out” the badness.
• For a deterministic algorithm, there might be only few bad instances
but a smart adversary will manage to select one of those instances.
• For a randomized algorithm, there could be a small probability of
poor performance on any instance but the likely performance is good
for all the instances.
• So now your adversary can only hope that you are unlucky...

Figure from the book: The Nature of Computation (2011).

Randomized Algorithms 8 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

• We first discuss a problem in graph theory, the Min-Cut problem,
where the goal is to find the smallest cut in a given graph G (V , E )
with set of vertices V and set of edges E .
A cut is defined as a subset of the edges of G whose removal causes a
partition of the vertices in two sets.
• The size of the cut corresponds to the number of its edges (we will
consider unweighted graphs).
• This problem has applications (among others) for the assessment of
the vulnerability of networks.
Min-Cut problem
Input: An undirected, unweighted and connected graph G (V , E ).
Question: What is the size of the smallest cut?
• Note: do not confuse this problem with the Max Flow-Min Cut
problem!
Randomized Algorithms 9 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

• We can solve this problem by iteratively solving the max flow problem
on graph G after assigning to each edge a capacity value equal to one.
• Select an arbitrary source node s. For all possible destination nodes t,
run, e.g, the Edmonds-Karp algorithm to find the max flow and a
corresponding Min Cut in G .
• The complexity of Edmonds-Karp algorithm is O(nm2 ), where n is
the number of vertices and m is the number of edges of G .
• Since the number of iterations is (n − 1), we get a deterministic
algorithm with a polynomial running time of O((nm)2 ).
• This procedure and its running time are not so spectacular...
(the running time could be further improved with other Max-Flow
algorithms but not significantly)
• We focus on a simple and elegant randomized algorithm given by
David Karger in 1993.
Randomized Algorithms 10 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

• Karger’s algorithm takes as input a graph G (V , E ) and outputs a cut

C ⊆ E.
• Pseudo-code of the algorithm:
1 Choose randomly an edge e.
2 Remove edge e and merge its vertices into a single vertex.
3 If there are only two vertices left, fill set C with the edges between the
two vertices. Return C.
4 Else go to Step 1.
• Basically the algorithm randomly contracts edges and correspondingly
merges vertices until only two vertices remain in the graph
(note that during the iterations of the algorithm there can be multiple
edges between some pairs of vertices).
• The surviving edges connecting the two remaining vertices constitute
a cut for graph G .

Randomized Algorithms 11 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

Example from the book: The Nature of Computation (2011).

• In the example the algorithm finds a minimum cut of size 2.

• How good is a cut computed by Karger’s algorithm in general? Let’s
find it out...
• Denote by Cmin the minimum cut (or one of the possible minimum
cuts) and denote the size of this cut by k (i.e. |Cmin | = k).
Randomized Algorithms 12 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

• Cut C coincides with Cmin only if the corresponding k edges are not
contracted by the algorithm (they survive till the end).
• Consider the iteration of the algorithm where there are t vertices in
the graph. Each vertex must have at least k edges...
• ...or else if a vertex has less than k edges, we can select them and get
a cut of size < k.
• Hence there are at least t(k/2) edges left in G .
• The probability than none of the k edges of Cmin is selected at
the considered iteration is:
k k t −2
1− ≥1− = ,
#edges tk/2 t

where #edges is the number of edges left in the graph.

Randomized Algorithms 13 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

• The probability p that we get Cmin when Karger’s algorithm

terminates is equal to the product of the previous probability over all
the (n − 2) iterations of the algorithm.
• Karger’s algorithm starts with n vertices in the graph and stops when
only two vertices are left. So we have t (the number of vertices left at
each iteration) that goes from n to 3.
• So we have
t=n
Y t −2 1 · 2 . . . (n − 2) 2
p≥ = = .
t 3 · 4...n n(n − 1)
t=3

• The probability of success (p) of a run of Karger’s algorithm is thus

Ω( n12 ) (roughly speaking ≥ n12 ).
• This does not seem an impressive result but...

Randomized Algorithms 14 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

Boosting technique:
• We can consider 1/p (O(n2 )) independent runs of Karger’s algorithm
and increase the overall probability of success. The probability that
none of the attempts computes Cmin is
1 1
(1 − p) p ≤
e
(by using inequality 1 − x ≤ e−x )
• The probability that at least one run succeeds is thus ≥ 1 − 1e ≈ 0.63
(constant probability).
• We can get a high probability of success 1 − o(1) (i.e. close to 1))
by just increasing the attempts by a factor ln n ⇒

Randomized Algorithms 15 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

( p1 ) ln n 1
⇒ (1 − p) ≤ e− ln n = = o(1) (if n >> 0)
n

• When the number of vertices in the graph is large, with a polynomial

number of attempts the algorithm finds a minimum cut with a
probability arbitrarily close to 1!
• Karger’s algorithm can be implemented to run with time complexity
O(m).
• Conclusion: we obtain a polynomial time and elegant algorithm that
succeeds with high probability...
...and with a running time of O(mn2 ln n) that is fully competitive
with the running time of the best known deterministic algorithms.

Randomized Algorithms 16 / 29
 Decision Making and Optimization

Min-Cut problem and Karger’s algorithm

Final remarks:
• Karger’s algorithm can be implemented by running Kruskal’s
algorithm for the minimum spanning tree problem!
The steps are:
- First randomly shuffle the order of the edges (for unweighted graphs)
- Run Kruskal’s algorithm to get a minimum spanning tree.
- Remove the last edge added to obtain a partition of the vertices and
a corresponding cut.
• Karger’s algorithm does not work for the s-t Min Cut problem where
two vertices s and t are required to be in different sets.

Randomized Algorithms 17 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• K-SAT problems are very famous problems in Computer Science.
• Consider a set of n boolean variables xi (i = 1, . . . , n) and a formula
φ in conjunctive form:
φ = C1 ∧ C2 ∧ . . . Cm ,
where each clause Ci has at most k literals.
• The goal is to find an assignment of the variables (a truth
assignment) that satisfies all the clauses simultaneously.
• A literal is either a variable xi (positive literal) or its negation x̄i
(negative literal). For a positive literal, setting xi = 1 makes a clause
satisfied (or true) while for a negative literal setting xi = 0 satisfies
the clause.
• Example of a clause for 3-SAT: (x1 ∨ x¯7 ∨ x13 )
The clause is true if at least one literal satisfies it, e.g. x7 = 0 or
x1 = 1.
Randomized Algorithms 18 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• To possibly find a solution for a K-SAT formula, we can perform a

random walk in the space of variables.
• Starting with a random assignment of the variables (a random point
in the space), we flip the values of the variables one by one until we
possibly “stumble” upon a solution.
• This gives a simple randomized algorithm denoted as WalkSAT.

Randomized Algorithms 19 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• WalkSAT can be stated as follows:
1 Start with a uniformly random assignment B.
2 If B satisfies φ, return B.
3 Else:
choose an unsatisfied clause at random.
choose a variable xi at random among all the variables appearing in the
clause.
Flip xi (i.e. change its current value) and update B.
4 If a Time Limit is not reached, go to Step 2.
5 Return “don’t know if a solution exists”.
• Once you flip a variable to satisfy a clause, you could make other
clauses unsatisfied.
• How can we evaluate the expected performance of WalkSAT
algorithm?
• The statistical properties of this kind of random walks sound
complicated.
Randomized Algorithms 20 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• We can still compare the differences between a WalkSAT assignment

B and an assignment A that satisfies the boolean formula (as we did
for the analysis of Karger’s algorithm).
• More precisely, we will consider the Hamming distance d between A
and B, namely the number of variables having a different value in A
and B.
• Thus WalkSAT succeeds if d = 0 =⇒ B = A.
• The algorithm also succeeds if it finds another satisfying assignment
earlier along the iterations but we do not consider this possibility in
the analysis.

Randomized Algorithms 21 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• Consider an unsatisfied clause c selected by WalkSAT.

• If by chance we change the value of a variable on which A and B
disagree, assignment B would get closer to A in Hamming distance.
• Conversely, if we flip a variable on which the assignments agree, the
Hamming distance between A and B would increase.
• In the worst case, A satisfies a clause c with just one variable
(disagreeing with B on that variable) while A and B agree on the
other (k − 1) variables.
• Hence d will decrease or increase with the following probabilities:

1 k −1
Prob[∆d = −1] = , Prob[∆d = +1] = .
k k

Randomized Algorithms 22 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• Which is the probability that WalkSAT obtains assignment A starting
from a random assignment B?
• This corresponds to the probability p(d) that we obtain a Hamming
distance of 0 starting from a value of d.
• We assume that d can range from 0 to +∞.
• Probability p(d) can be recursively expressed as:
1 k −1
p(d) = p(d − 1) + p(d + 1).
k k
• Some boundary conditions:
p(0) = 1 (absorbing state);
p(+∞) = 0 (if we are very far from the origin, we probably move on
the “right” rather than on the “left”).
• With these conditions, we have
p(d) = (k − 1)−d . (Let’s prove it) ⇒
Randomized Algorithms 23 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• Let e = 1 k−1
k and f = k with e + f = 1. We have:

p(d)(e + f ) = ep(d − 1) + fp(d + 1)

e
=⇒ p(d + 1) − p(d) = (p(d) − p(d − 1))
f
• Let y = e/f = (k − 1)−1 (< 1). We have the following recursive
equations:
p(1) − p(0) = p(1) − 1
p(2) − p(1) = y (p(1) − p(0)) = y (p(1) − 1)
p(3) − p(2) = y (p(2) − p(1)) = y 2 (p(1) − 1)
...
p(d) − p(d − 1) = y (p(d − 1) − p(d − 2)) = y (d−1) (p(1) − 1).

Randomized Algorithms 24 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• By summing up all the equations we get

d−1
X 1 − yd
p(d) − p(0) = y i (p(1) − 1) = (p(1) − 1).
1−y
i=0

• By using boundary conditions p(0) = 1 and p(+∞) = 0, we have

1
p(+∞) = 1 + (p(1) − 1) = 0 =⇒ p(1) = y .
1−y
• Hence
1 − yd
p(d) = 1 + (y − 1) = y d = (k − 1)−d .
1−y

Randomized Algorithms 25 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• In order to compute the probability of success PS of WalkSAT, we

have to average over all possible 2n starting assignments B, i.e.:
1 X
PS = Prob[WalkSAT succeeds starting from B]
2n
B

n   n  
1 X n 1 X n
=⇒ PS = n p(d) = n (k − 1)−d =
2 d 2 d
d=0 d=0
 −n
2(k − 1)
=⇒ PS = .
k
• To get the last expression we used the binomial formula
Pn n i (n−i) 1
= (a + b)n with a = k−1


i=0 i a b and b = 1.
• For k = 3 (3-SAT), we have PS = 43 −n (exponentially small).

Randomized Algorithms 26 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• As we saw for Karger’s algorithm, if we try 1/PS independent runs of
WalkSAT, we then can succeed with constant probability if the initial
formula is satisfiable.
• If we perform n/PS attempts, we succeed with probability 1 − e−n
(exponentially close to 1).
• Notice that WalkSAT could run for an unbounded number of steps.
What about the running time of this algorithm?
• We discuss in the next slides that O(n) steps are “enough”...
• For 3-SAT we get a running time of
 n
4
poly (n)
3
• The running time is still large but it is lower than the running time of
a brute force approach (2n ). Moreover, this running time is
competitive with the state-of-the art deterministic algorithms for the
problem.
Randomized Algorithms 27 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• For 3-SAT, we show now that running WalkSAT for 3d steps only
(O(n) as d ≤ n) is sufficient to reach the same probability of success
of a single run of WalkSAT that can walk forever.
• So if we do not find a solution after O(n) iterations of the algorithm,
we should stop and try another random restart!
• The following analysis shows that fresh restarts make sense as in 3d
steps we already get (apart from a polynomial factor) the probability
of success p(d) = 2−d given by allowing WalkSAT to walk an
unbounded number of steps.
• Let’s compute the probability Prob3d that WalkSAT finds a satisfying
assignment after 3d steps.

Randomized Algorithms 28 / 29
 Decision Making and Optimization

K-SAT problem and WalkSAT algorithm

• In 3-SAT we have p(d) = 2−d , Prob[∆d = −1] = 13 and
Prob[∆d = +1] = 23 .
• To compute Prob3d we have to perform 2d steps to the left and d
steps to the right (in any order) to reach 0 from a given Hamming
distance d (note: we can consider in the analysis also negative values
of d).
• We have
   2d  d
3d 1 2 (3d)! 2d
Prob3d = =
d 3 3 d!(2d)! 33d
r  −d 
3 1 2
≈ d
=O
4πd 2 d
The last
√ expression is derived by using Stirling’s approximation
n n


n! ≈ 2πn e for n → +∞.
Randomized Algorithms 29 / 29