Part II
Types and basic design methods for randomized algorithms
Chapter 2. DESIGN METHODS for RANDOMIZED ALGORITHMS
In this chapter:
1 Main types of randomized algorithms are introduced
and illustrated.
2 Main design methods for randomized algorithms are
introduced and illustrated.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 2/58
BASIC PROBABILITIES FOR RANDOMIZED ALGORITHMS
Let us consider any decision problem P.
For any randomized algorithm A for P, and for any input x of A, let the set SA,x of
all runs of A on x be the main sample space for the analysis of A on the input x.
If one chooses the random variable VA,x that assigns 1 (0) to any run of A on x with
the correct (wrong) output, then the expectation value of VA,x is exactly the success
probability of A on x.
The probability of the complementary event is called the error probability of A on x.
If one takes a random variable that assigns to every computation its complexity
(number of steps), then the expectation of this random variable equals the expected
time complexity of A on x.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 3/58
CLASSIFICATION of RANDOMIZED ALGORITHMS
As Las Vegas algorithms are called those algorithms that never produce wrong
outcomes, though sometimes they may produce the outcome “I don’t know”
(usually denoted as ??). (However, with bounded probability only.)
A one-sided-error Monte Carlo algorithm (1MC), for a language L, is an algorithm
that accepts with probability at least 1
2
any input x ∈ L and rejects for sure any
input not in L; (The error probability of such algorithms converges to 0 with
exponential speed if a number of independent runs are executed.)
A bounded-error Monte Carlo algorithm (2MC) A, for a function F, is an algorithm
for which there exists a constant ε > 0 such that, for any input x, the algorithm
computes the correct output A(x) = F(x), with probability at least 1/2 + ε. (The
error probability of such an algorithm can be reduced to an arbitrarily small given
constant δ using only constantly many (depending on δ) runs.)
A (unbounded error) Monte Carlo algorithm (UMC) is an algorithm that, for any
input x, computes the correct output with probability at least 1/2. (To reduce the
error probability of such an algorithm below a given constant, exponentially many
runs may be needed.)
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 4/58
RANDOMIZED ALGORITHMS DESIGN PARADIGMS - I
Foiling the adversary: One finds a set of deterministic
algorithms such that, for each input most of these
algorithms compute correct results efficiently and one takes
as the randomized algorithm a probability distribution over
such a set of deterministic algorithms. (The idea is to
overcome such a situation when for each deterministic
algorithm there exist bad inputs (for which the algorithm
gives wrong result or computes inefficiently.)
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 5/58
RANDOMIZED ALGORITHMS DESIGN PARADIGMS - II
Abundance of witnesses. A witness y for an input x and
problem P is information with which one can solve the
problem P for input x more efficiently than without it. If
one finds a set S such that at least half of its elements are
witnesses for P and x, then a random choice of an
element in the set S leads to a witness for P and x,with
probability at least 1
2.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 6/58
RANDOMIZED ALGORITHMS DESIGN PARADIGMS - III
Fingerprinting. For solving various problems it can be
much more efficient to work with very small fingerprints
(hashes) of large objects than with such large objects
directly.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 7/58
RANDOMIZED ALGORITHMS DESIGN PARADIGMS - IV
Random sampling. If there are in a set sufficiently many objects we are looking for,
then a random sampling in that set can provide such an object with sufficiently high
probability. This method is also called probabilistic method.
Random rounding.: A hard to solve optimization problem P is transferred to an easy
to solve optimization problem P0, just by increasing the size of the solution space, in
such a way that the outcomes of any solution of the new problem can be used to
create an efficient randomized algorithm to solve the original problem P.
An amplification of the success probability of a randomized algorithm can be
achieved by repeating independent computations on the same input (but, of course,
with different random auxiliary inputs).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 8/58
STRINGS EQUALITY PROBLEM
Notation. For a binary vector/string x = x1x2 . . . xn let
Number(x) =
n
i=1
xi 2n−i
.
Problem Each of the two parties, say A and B has one n-bit string. By communication
parties have to decide whether their strings are equal. How to do that efficiently?
Each deterministic protocol clearly requires sending at least n bits in the worth case.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 9/58
STRINGS EQUALITY PROBLEM - RANDOMIZED PROTOCOL
Initial situation.
Party A has a binary string x = x1x2 . . . xn.
Party B has a binary string y = y1y2 . . . yn.
Protocol
1 Alice chooses, randomly, a prime p ≤ n2
and sends to Bob p and the binary
representation of the number
s = Number(x) mod p;
2 Bob computes
t = Number(y) mod p
and declares that x = y iff s = t.
Analysis The protocol requires to send at most
2 lg n2
≤ 4 lg n bits.
Example: For n = 1016
the protocol requires to send at most 256 bits.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 10/58
ERROR ANALYSIS
Let us say that a prime 2 < p < n2
is bad for a pair (x, y), x = y, if the above protocol
for such an input pair (x, y) and such a choice of prime yields a wrong answer.
Notation Prim(m) = number of primes smaller than m.
Error probability for an input (x, y) is
number of bad primes for (x, y)
Prim(n2)
.
Since, by Prime number theorem, Prim(m) > m/ ln m for m > 69, we have that for n ≥ 9
Prim(n2
) >
n2
2 ln n
.
The so-called Prime number theorem says that there are approximately n
ln n
primes among
the first n integers.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 11/58
NUMBER Of BAD PRIMES
Lemma Number of bad primes for x = y is at most n − 1.
Proof. A prime p is clearly bad for the pair (x, y), x = y, if and only if p divides the
number
w = |Number(x) − Number(y)| < 2n
Observe that w can be uniquely factorized as
w = pe1
1 pe2
2 . . . p
ek
k
where p1 < p2 < . . . < pk are primes.
We can show that k ≤ n − 1. Indeed, if k ≥ n, then
w ≥ 1 · 2 · 3 . . . n = n! > 2n
what is a contradiction.
Probability of the error of the above equality protocol is therefore:
n − 1
Prim(n2)
≤
n − 1
n2/ ln n2
≤
ln n2
n
=
2 ln n
n
which is at most 0.369 · 10−14
in case n = 1016
.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 12/58
PROBABILITY AMPLIFICATION
In case the above protocol is repeated 10 times, each time with a different prime, and the
answer is x = y each time, then the probability of an error is at most
ln n2
n
10
and therefore, for n = 1016
, the error probability is at most
0.47 · 10−141
.
Reminder Probability of the correct output is at least
1 −
2 ln n
n
.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 13/58
A LAS VEGAS ALGORITHM WITH ??
Problem Alice has 10 strings xi ∈ {0, 1}n
, n > 500 and Bob has also 10 strings
yi ∈ {0, 1}n
. The task is to determine whether xi = yi for some 1 ≤ i ≤ 10.
One can show that each deterministic protocol has to exchange in the worth case 10n
bits. Therefore no deterministic algorithm is essentially more efficient than sending all
bits from Alice to Bob and then to let Bob to make comparisons.
We show the existence of a Las Vegas algorithm to solve the above problem (that is to
decide whether such an i exists) with communication complexity
n + O(lg n).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 14/58
PROTOCOL
Alice randomly chooses 10 primes p1, . . . , p10, each smaller than n2
, then, computes
all
si = Number(xi ) mod pi , i ∈ {1, .2, . . . , 10}
and, finally, sends to Bob 20 numbers:
p1, . . . , p10, s1, . . . , s10.
Bob computes all numbers
ri = Number(yi ) mod pi
and compares elements in all pairs (si , ri ).
If si = ri for all i, Bob outputs NO (0);
otherwise, if j is the smallest integer such that sj = rj , then Bob sends Alice the pair
(j, yj ).
If xj = yj , Alice outputs YES (1);
otherwise she outputs ?? (because it may exist other k with xk = yk ).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 15/58
COMPLEXITY ANALYSIS of the PROTOCOL 1/2
The above protocol exchanges 20 lg n2
+ n + 4 bits - {4 bits are needed to send j}.
A proof that the protocol is a Las Vegas protocol
If xi = yi for all i, then the probability that
Number(xi ) mod pi = Number(yi ) mod pi
for all i, and therefore the probability that the above protocol produces the correct
output is at least
1 −
2 ln n
n
10
because, according to the analysis of the strings equality algorithm, the probability
that Number(xi ) mod pi = Number(yi ) mod pi is at least 1 − 2 ln n
n
.
Moreover, it can be shown that
1 −
2 ln n
n
10
≥ 1 −
20 ln n
n
≥
1
2
for sufficiently large n
In the complementary case - if there exists a j such that
Number(xj ) mod pj = Number(yj ) mod pj
then protocol outputs ??, what is O.K., and what means that the protocol cannot
confirm the hypothesis xj = yj .prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 16/58
COMPLEXITY ANALYSIS of the PROTOCOL 2/2
Let us now consider the case that there is an j such that xj = yj and j0 be the
smallest such j.
Protocol then accepts the input iff
Number(xi ) mod pi = Number(xi ) mod pi
for all i < j0. Let us denote such an event by Ej0 .
If j0 = 1, then the protocol accepts the input with certainty. If j0 > 1, then, as
discussed before, probability of the event Ej0 is at least
1 −
2 ln n
n
j0−1
≥ 1 −
2(j0 − 1) ln n
n
for sufficiently large n.
and therefore the protocol outputs YES (1) with probability at least 1 − 18 ln n
n
, which
is larger than 1
2
for all n ≥ 189.
In the complementary case, when there is an l < j0 such that
Number(xl ) mod pl = Number(xl ) mod pl
the protocol produces as output ??.
The above protocol is therefore indeed a Las Vegas protocol.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 17/58
TWO TYPES of LAS VEGAS ALGORITHMS
There are two types of Las Vegas algorithms:
Algorithms that never produce ??.
Algorithms that may produce ??.
Note: Las Vegas algorithms may not terminate for some inputs!!!
Claim Any Las Vegas algorithm A1 can be converted to a Las Vegas algorithm A2 that
solves the same problem and never produces ??.
Construction of A2 is simple. Each time A1 is to produce the output ??, what can be
done only with bounded probability, a new run of A1 is initialized with the same input.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 18/58
AMPLIFICATION of 1MC ALGORITHMS
Error probability of 1MC algorithms decreases exponentially with the number of
repetitions of computations.
Indeed, if we have k independent runs of the algorithm and one output is 0 (rejection),
then the input is rejected with certainty.
If all outputs are 1 (acceptance), then the output will be YES (acceptance) and the error
probability is at most 1
2
k
.
Because of the exponential decrease of error probability using repeated applications, 1MC
algorithms are very popular.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 19/58
AMPLIFICATION of 2MC ALGORITHMS
Let A be a 2MC algorithm for a function F and ε > 0 such that
Prob(A(x) = F(x)) ≥
1
2
+ ε.
For any integer k let Ak be the algorithm that performs k independent runs of A and if
there is an α that appears at least k
2
times as the output, then Ak produces α as the
output; if there is no such an α, Ak produces ?? as the output.
One can show that if an δ > 0 is fixed, then
Prob(Ak (x) = F(x)) ≥ 1 − δ
if
k ≥
2 ln δ
ln(1 − 4ε2)
.
If ε and δ are considered as constant, then so is k and therefore
TimeAk (n) = O(TimeA(n)).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 20/58
2MC versus UMC algorithms
Basic question: What is the difference between 2MC and UMC algorithms?
Answer: For an UMC algorithm A it may happen that the distance between the error
probability and 1
2
tends to 0 with growing input size.
As a consequence, if we design, given an δ > 0, an algorithm Ak , that performs k
independent runs of A and
Prob(Ak (x)) = F(x)) > 1 − δ
then running time of Ak may be exponential in the input length.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 21/58
TESTING of STRAIGHTLINE PROGRAMS
Given is a straightline program that consists of a sequence of assignments; the first
assignment is a ← 1 and in each other assignment two previously designed variables are
either added, or subtracted or multiplied.
How to check whether the outcome of such a program will be 0? Example of such a
straightline program:
a = 1
b = a + a
c = b × b
d = c × c
e = d × d
f = e − a
g = d − a
h = d + a
i = g × h
j = f − i
(The catch (problem) is that numbers created during such a program can be enormous.)
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 22/58
RANDOMIZED ALGORITHM
1. If number of assignment statements is n, pick a random prime p with 2n2
bits.
2. Perform the given program, but do all computations modulo p.
This algorithm runs in time polynomial in n.
If such a randomized algorithm provides a non-zero number as the output, the output of
the original program (with full computations, not modulo ones) is also non-zero.
If the output is zero, how confident we can be that the original program evaluates also to
0?
Let x be the outcome of the original program. Clearly, |x| ≤ 22n
.
By Prime Number Theorem, number of primes with 2n2
bits is about 22n2
2n2 and since this
number is much bigger than 22n
, most of those primes can not divide x (unless x = 0).
This means that if we pick a random prime and it does not divide x, then we can be very
confident (but not certain) that x = 0.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 23/58
SECRET SHARING between TWO
Problem: The task is to ”partition” a secret S between two parties P1 and P2 in such a
way that none of the parties alone has slightest idea what S is, but if they get together
they can easily determine S.
Method: A moderator distributes a binary-string secret S, between two parties P1 and P2
by choosing a random binary string b, of the same length as s, and sends:
b to P1 and
s ⊕ b to P2.
This way, none of the parties P1 and P2 alone has a slightest idea about s, but both
together easily recover s by computing
b ⊕ (s ⊕ b) = s.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 24/58
PERFECT MATCHING ALGORITHM - I.
Let G = V , E be an undirected graph. A subset X ⊆ E is said to be a matching of G if
no two edges in X have a common node.
A matching is said to be a perfect matching if it covers all nodes of G.
Example Which of the graphs in the next figure has a perfect matching?
There are polynomial time algorithms to decide whether a given graph has perfect
matching, but none is so simple as the randomized algorithm based on so called Tutte
theorem presented bellow.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 25/58
TUTTE MATRIX
Basic concept: Tutte matrix of a graph
Let G = V , E be a bipartite graph with nodes V = {1, 2, . . . , n} The Tutte matrix
AG = {aij }n
i,j=1 of G is defined by (xij are variables, all different for different i, j)
aij =



xij if (i, j) ∈ E, i < j;
−xij if (i, j) ∈ E, i > j;
0 if (i, j) ∈ E
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 26/58
TUTTE THEOREM - I.
Example For the graph of six nodes at which node 1 is connected with nodes 4 and 5,
node 2 with nodes 5 and 6 and the node 3 is connected with nodes 5 and 6 the Tutte
matrix has the form:








0 0 0 x14 x15 0
0 0 0 0 x25 x26
0 0 0 0 x35 x36
−x14 0 0 0 0 0
−x15 −x25 −x35 0 0 0
0 −x26 −x36 0 0 0








Tutte theorem A graph G = V , E has a perfect matching iff the determinant of the
corresponding Tutte matrix is not identically zero.
Proof The determinant of AG equals π σπ
n
i=1 aiπ(i) where π are permutations of
{1, 2, . . . , n} and σπ = 1 (σπ = −1) if π is a product of an even (odd) number of
transpositions.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 27/58
TUTTE THEOREM - OBSERVATIONS
Observation 1 For a permutation π, n
i=1 aiπ(i) = 0 iff Gπ = {(i, π(i)), 1 ≤ i ≤ n} is a
subgraph of G.
Observation 2 Permutations π with at least one odd cycle do not contribute at all to the
determinant of A, because to each such permutation π there is a permutation π such
that n
i=1 aiπ(i) = − n
i=1 aiπ (i)
Observation 3 It is sufficient to consider permutations π such that Gπ consists only of
even cycles. Let permutation πr
be obtained from π by reversing all cycles.
Notation For a perfect matching E let tE denote the product of the a s corresponding
to the edges of E .
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 28/58
TUTTE THEOREM - CASE ANALYSIS
Case I π = πr
⇒ Gπ consist of the cycles of length 2, π corresponds to a perfect
matching E such that n
i=1 aiπ(i) = (tE )2
.
Case II π = πr
In this case both π and πr
correspond to the union of two perfect
matchings E , and E obtained by alternatively selecting edges within the cycles so that
n
i=1
aiπ(i) +
n
i=1
aiπr (i) = 2tE tE .
Conclusion
det(AG ) = (tE1
+ · · · + tEk
)2
where Ei denotes i-th perfect matching.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 29/58
EXPLANATION
Let us illustrate claims from the previous slide for a graph with 4 nodes: 1, 2, 3 ,4
Case 1. Let us have edges 1-2, 3-4 only and permutation
π = πr
: 1 → 2, 2 → 1, 3 → 4, 4 → 3
Perffect matching E is 1 − 2, 3 − 4, tE = a12a34 and
4
i=1
aiπ(i) = a12a12a34a34 = (TE )2
Case 2. Let us have edges 1-2, 2-3, 3-4, 4-1 and permutations:
π : 1 → 2 → 3 → 4 → 1, πr
: 1 → 4 → 3 → 2 → 1
tE = a12a34, tE = a41a23
4
i=1
aiπ(i) +
4
i=1
aiπr (i) = a12a23a34a41 + a12a23a34a41 = 2tE tE .
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 30/58
RANDOM SELECT
Problem Given is a set S = {a1, . . . , an} of n > 0 different numbers, and 1 ≤ k ≤ n, find
the k-th smallest number from S.
A naive way to solve the problem is to sort at first S. This requires O(n lg n)
comparisons. The following randomized algorithm RSELECT can do that in O(n) steps
Algorithm RSELECT(S, k))
1 If n = 1 output a1.
2 Otherwise choose i ∈r {1, 2, . . . , n} and
1 compute
S< = {b ∈ S | b < ai }
S> = {b ∈ S | b > ai }
2 if |S<| ≥ k then RSELECT(S<, k);
else if |S<| = k − 1 then output ai ;
else
RSELECT(A>, k − |A<| − 1)
This is clearly a Las Vegas algorithm.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 31/58
CLASSIFICATION of RANDOMIZED OPTIMIZATION
ALGORITHMS
Classification of the randomized algorithms we had so far was based on the frequency of
correct outputs and it is suited only for classification of algorithms for decision problems
and for computation of functions, but not for optimization problems.
In case of optimization problems, we do not take as the output the most frequent output
from several runs, but the best output according to some optimization criterion.
Moreover, in case of optimization problems our goal is not always to find an optimal
solution. We are usually quite happy to find an almost (and feasible) solution - whose
cost (quality) does not differ much from the cost (quality) of an optimal solution.
All that means that a different approach to the classification of randomized
approximation algorithms is needed.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 32/58
ILLUSTRATION
If a randomized algorithm A computes an optimal solution for an input x with probability
at least 1
|x|
, then it does not mean that A is not useful.
Indeed, one can execute |x| independent runs of A on given input x, call that to be the
Ax algorithm, and then take the best output of all of them. Let us ask now what is the
probability of success of Ax .
Probability of computing no optimal solution in one run is at most
1 −
1
|x|
and therefore the probability that Ax does not find an optimal solution in |x| independent
runs is at most
(1 −
1
|x|
)|x|
<
1
e
and we have a constant probability 1 − 1
e
of computing an optimal solution.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 33/58
DEFINITION of OPTIMIZATION PROBLEMS
Definition An optimization problem is a 6-tuple P = (ΣI , ΣO , L, M, cost, goal), where
1 ΣI is an input alphabet;
2 ΣO is an output alphabet;
3 L ⊆ Σ∗
I is the language of feasible inputs and any x ∈ L is called a problem instance
of P;
4 M is a function from L to 2Σ∗
O , and for each x ∈ L, M(x) is the set of feasible
solutions for x;
5 cost is a function: x∈L(M(x) × x) → R+
, called cost function;
6 goal ∈ (minimum, maximum) is an objective.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 34/58
SOLVING an OPTIMIZATION PROBLEM
Observe that to solve an optimization problem is more as computing a relation, than as
computing a function, because we are usually happy with finding one of the optimal
solutions or even with a solution quite close to an optimal one.
A feasible solution α ∈ M(x) is called optimal for the problem instance x of P if
cost(α, x) = goal{cost(β, x) | β ∈ M(x)}.
An algorithm A is said to solve P if, for any x ∈ L,
A(x) ∈ M(x);
cost(A(x), x) = goal{cost(β, x) | β ∈ M(x)}
If the goal is to find minimum (maximum) we talk about a minimization (maximization)
problem.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 35/58
EXAMPLE - TRAVELING SALESMAN PROBLEM
Input: A weighted complete graph (G, c), where G = (V , E), V = {v1, . . . , vn},
E ⊂ V × V and c : E → N+
is a cost function.
Hamiltonian cycles: For any problem instance (G, c), let M(G, c) be the set of
Hamiltonian cycles of G - each such cycle is represented by a sequence of vertices
vi1 , vi2 , . . . , vin , vi1 , where i1, i2, . . . , in is a permutation of (1, 2, . . . , n).
Costs of Hamiltonian cycles: For every Hamiltonian cycle
H = (vi1 , vi2 , . . . , vin , vi1 ) ∈ M(G, c)
cost((vi1 , vi2 , . . . , vin , vi1 ), (G, c)) =
n
j=1
c((vij , vi(j+1) mod n
)).
Goal: minimum - to find a Hamiltonian cycle with minimum cost.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 36/58
EXAMPLE
v1
v2
v3
v4
v5
8
1
2
71
12
3
1
1
cost((v1, v2, v3, v4, v5, v1), (G, c)) = 19
cost((v1, v5, v3, v2, v4, v1), (G, c) = 5
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 37/58
INTEGER LINEAR PROGRAMMING
Given is a system of linear equations and a linear function over variables of this
equations. The task is to find a solution to the system of equations such that the value
of the linear function is minimized. More formally:
Input An m × n matrix and two vectors
A = {aij }i=m,j=n
i,j=1 , b = (b1, . . . , bm)T
, c = (c1, . . . , cn)
with integer entries.
Set of feasible solutions: M(A, b, c) = {X = (x1, . . . , xn)T
| AX = b}.
Cost of a solution: For X = (x1, . . . , xn) ∈ M(A, b, c)
cost(X, (A, b, c)) = c · X =
n
i=1
ci xi .
Goal: minimum
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 38/58
QUANTIFICATION of “ALMOST OPTIMAL SOLUTIONS” 1/2
Many very important optimization problems are NP-hard and so we know only
exponential time algorithms for finding optimal solutions.
New idea is to jump from exponential to polynomial time by weakening the requirements
- to be satisfied with almost optimal solutions. To quantize that tries the next definition.
Definition Let P = (ΣI , ΣO , L, M, cost, goal) be an optimization problem. We say that
A is a consistent algorithm for P if, for every x ∈ L, the output A(x) is a feasible solution
for x - that is A(x) ∈ M(x).
We say that an approximation algorithm A mapping each instance x of an optimization
problem P to one of its feasible solutions has the ratio bound ρA(n) and the relative error
bound εA(n) if
max
|x|=n
cost(A(x))
cost(Opt(x))
,
cost(Opt(x))
cost(A(x))
≤ ρA(n)
and
max
|x|=n
|cost(A(x)) − cost(Opt(x))|
max{cost(Opt(x)), cost(A(x))
≤ εA(n)
Both definitions are chosen to correspond to our intuition and to apply simultaneously to
minimization and maximization problems. Both these bounds compare an approximation
solution with the optimal one, but in two different ways.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 39/58
QUANTIFICATION of “ALMOST OPTIMAL SOLUTIONS” 2/2
For any δ > 1 we say that A is a δ-approximation
algorithm for P if, for every integer n, ρA(n) ≤ δ.
The ratio bound is never less than one. An optimal
algorithm has ratio bound 1. The larger the best possible
ratio bound of an approximation algorithm, the worse is
the algorithm.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 40/58
Approximation algorithms for NP problems
Two general problems concerning approximation of NP-complete problems are of special
interest and importance.
The constant relative error bound problem: Given an NP-complete optimization problem
P with a cost of solution function c and an ε > 0, does there exist an approximation
polynomial time algorithm for P with the relative error bound ε?
The approximation scheme problem: Given an NP-complete problem P, does there exist
for P with a cost of solution function c a polynomial time algorithm for designing, given
an ε > 0 and an input instance x, an approximation for P and x with the relative error
bound ε?
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 41/58
Approximation thresholds
It is said that an algorithm A is an ε-approximation algorithm for an optimization
problem P if ε is its relative error bound.
The approximation threshold for P is the greatest lower bound of all ε > 0 such that
there is a polynomial time ε-approximation algorithm for P.
It can be shown that NP-complete problems can differ very much with respect to their
approximation thresholds.
Note that if an optimization problem P has an approximation threshold 0, this means
that a (polynomial time) approximation arbitrarily close to the optimum is possible.
Note also that if P has approximation threshold 1, this means that no universal
(polynomial time) approximation method is possible.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 42/58
Examples
Example 1 The approximation threshold for the optimization version of the
KNAPSACK PROBLEM is 0.
Example 2 The approximation threshold for the VERTEX COVERPROBLEM is ≤ 1
2
.
Example 3 Unless P = NP, thee approximation threshold for the TRAVELING
SALESMAN PROBLEM is 1.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 43/58
WHY TO APPLY RANDOMIZATION in DISCRETE
OPTIMIZATIONS
One of the main goals in the area of discrete optimization is to improve the
approximation ratio. One tries to design randomized approximation algorithms that
produce feasible solutions whose cost (quality) is not very far from the optimal cost with
high probability. In the analysis of randomized algorithms we consider therefore the
approximation ratio as a random variable and the aim is then either
1 to estimate the expected value, E(Ratio), or
2 to guarantee that a certain approximation ratio is achieved with probability at least
1
2
.
These two different aims lead to two ways randomized approximation algorithms are
defined.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 44/58
Definition 1 Let P = (ΣI , ΣO , L, M, cost, goal) be an optimization problem. For any
δ > 1, a randomized algorithm A is called a randomized E[δ]-approximation algorithm
for P if
1 Prob(A(x) ∈ M(x)) = 1, and
2 E[RatioA(x) ≤ δ] ≥ 1
2
.
for every x ∈ L.
Definition Let P = (ΣI , ΣO , L, M, cost, goal) be an optimization problem.For any δ > 1,
a randomized algorithm A is called a randomized δ-approximation algorithm for P if
1 Prob(A(x) ∈ M(x)) = 1, and
2 Prob(RatioA(x) ≤ δ) ≥ 1
2
.
for every x ∈ L.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 45/58
Online algorithms
Another area in which randomization plays important role are online algorithms.
In practice the following problems are often of importance. One always obtains only a
part of the input that has to be processed immediately. Once this is done one obtains
another part of the input and has to process it again immediately, and so on - the input
can be infinitely long. Such problems are called online problems and algorithms to solve
them are called online algorithms.
Example Scheduling problem - immediate assigning of resources for requests coming one
after another.
Key question. How good can an online algorithm (that does not know the future) be in
comparison to an algorithm that knows the whole input (the future) from the beginning?
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 46/58
Evaluation of online algorithms
Let P == (Σi , Σ0, L, M, cost, goal) be an optimization problem that can be viewed as an
online problem1
An algorithm A is an online algorithm for P if, for every input
x = x1x2 . . . xn ∈ L the following conditions are satisfied:
1 For all i ∈ {1, . . . , n} x1x2 . . . xi is a feasible input.
2 A(x) ∈ M(x), i.e. A always computes a feasible solution.
3 For all i ∈ {1, . . . , n}, A(x1x2 . . . xi ) is a part of A(x), i.e. the decisions made for the
prefix x1x2 . . . xi of x cannot be changed any more.
For every input x ∈ L, the competitive ratio compA(x) of A on x is the number
compA(x) = max
OptP (x)
costA(x)
,
costA(x)
OptP (x)
where OptP (x) denotes the cost of an optimal solution for the instance x of the problem
P.
Let δ ≥ 1. We say that A is a δ-competitive algorithm for P if compA(x) ≤ δ for all
x ∈ L.
Let δ ≥ 1 be a real. We say that an online problem P is δ-hard if there does not exist
any d-competitive online algorithm for P with d < δ.
1
An optimization problem can be viewed as an online problem when each prefix y of every input x can be
viewed also as a problem instance, and one is required to provide a solution for y that has to remain unchanged
as a part of the solution for the whole input x.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 47/58
FACTORIZATION of INTEGERS
The fastest classical algorithm to factor m bit numbers requires time O(ecm1/3
(lg m)2/3
).
Shor’s factorization algorithm requires O(m2
lg2
m lg lg m) time on a quantum computer
and polynomial time on a classical computer.
Factorization of integers can be reduced to solution of several simple algorithmic
problems.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 48/58
FIRST REDUCTION
Lemma
If there is a polynomial time deterministic (randomized) [quantum] algorithm to find a
nontrivial solution of the modular quadratic equations
a2
≡ 1 (mod n),
then there is a polynomial time deterministic (randomized) [quantum] algorithm to
factorize integers.
Proof. Let a = ±1 be such that a2
≡ 1 (mod n). Since
a2
− 1 = (a + 1)(a − 1),
if n is not prime, then a prime factor of n has to be a prime factor of either a + 1 or
a − 1.
By using Euclid’s algorithm to compute
gcd(a + 1, n) and gcd(a − 1, n)
we can find, in O(lg n) steps, a prime factor of n.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 49/58
SECOND REDUCTION
The second key concept is that of period of the functions
fn,x (k) = xk
mod n.
It is the smallest integer r such that
fn,x (k + r) = fn,x (k)
for any k, i.e. the smallest r such that
xr
≡ 1 (mod n).
AN ALGORITHM TO SOLVE EQUATION x2
≡ 1 (mod n).
1 Choose randomly 1 < a < n.
2 Compute gcd(a, n). If gcd(a, n) = 1 we have a factor.
3 Find period r of function ak
mod n.
4 If r is odd or ar/2
≡ ±1 (mod n),then go to step 1; otherwise stop.
If this algorithm stops, then ar/2
is a non-trivial solution of the equation
x2
≡ 1 (mod n).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 50/58
EXAMPLE
Let n = 15. Select a < 15 such that gcd(a, 15) = 1.
{The set of such a is {2, 4, 7, 8, 11, 13, 14}}
Choose a = 11. Values of 11x
mod 15 are then
11, 1, 11, 1, 11, 1
what gives r = 2.
Hence ar/2
= 11 (mod 15). Therefore
gcd(15, 12) = 3, gcd(15, 10) = 5
For a = 14 we get again r = 2, but in this case
142/2
≡ −1 (mod 15)
and the following algorithm fails.
1 Choose randomly 1 < a < n.
2 Compute gcd(a, n). If gcd(a, n) = 1 we have a factor.
3 Find period r of function ak
mod n.
4 If r is odd or ar/2
≡ ±1 (mod n),then go to step 1; otherwise stop.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 51/58
EFFICIENCY of REDUCTION
Lemma
If 1 < a < n satisfying gcd(n, a) = 1 is selected in the above algorithm randomly and n is
not a power of prime, then
Pr{r is even and ar/2
≡ ±1} ≥
9
16
.
1 Choose randomly 1 < a < n.
2 Compute gcd(a, n). If gcd(a, n) = 1 we have a factor.
3
4 Find period r of function ak
mod n.
5 If r is odd or ar/2
≡ ±1 (mod n),then go to step 1; otherwise stop.
Corollary
If there is a polynomial time randomized [quantum] algorithm to compute the period of
the function
fn,a(k) = ak
mod n,
then there is a polynomial time randomized [quantum] algorithm to find non-trivial
solution of the equation a2
≡ 1 (mod n) (and therefore also to factorize integers).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 52/58
A GENERAL SCHEME FOR SHOR’S ALGORITHM
quantum
x
find period r
subroutine
r is
even?
r/2 r/2
z=1 ?
output z
no
yes
no
compute
z = gcd(a, n)
z = 1?
yes
no
z = max{gcd(n, a -1), gcd(n, a +1)}
yes
of function a mod n
choose randomly
a {2, ... ,n-1}
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 53/58
GENERATION of (PSEUDO) RANDOMNESS
There are nowadays several tools how to produce sufficiently good randomness:
Pseudo-random generators
Extractors of randomness
Quantum measurements - quantum random bits
generating devices (that are already produced
commercially).
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 54/58
PSEUDO-RANDOM GENERATORS
Definition - pseudorandom generator Let ln : {0, 1}n
→ {0, 1}Nn
be such that Nn >> n
for all n. A (computationally indistinguishable) pseudorandom generator with stretch
function ln, is an efficient deterministic algorithm which on input of a random n-bit seed
outputs an Nn-bit sequence which is computationally indistinguishable from a random
Nn-bit sequence.
It has been shown that if integer factoring is intractable, then the so-called BBS
pseudo-random generator, discussed below, is sufficiently good even for
cryptographic purposes.
Let n be an integer such that n mod 4 = 3. Choose randomly an x0 < n.
For i ≥ 0 let
xi+1 = x2
i mod n, bi = the least significant bit of xi
For each integer j, let BBSn,j (x0) = b0 . . . bj−1 be the first j bits of the pseudo-random
sequence generated from the seed x0 by the BBS pseudo-random generator.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 55/58
RANDOMNESS EXTRACTORS
Extractors are algorithms that produce from any long and weakly-random bitstring a
shorter, but more random, bitstring.
In other words, an extractor is a mapping which, when applied to high-entropy source
generates a shorter yet uniformly distributed output.
In a more general approach an extractor is an algorithm that converts a long weakly
random source and a truly random short seed into a uniformly distributed random output
(that is longer than the seed and shorter than the source).
An extractor is a certain kind of pseudorandom generator.
No extractor is currently know that has been proven to work when applied to any type of
high-entropy source.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 56/58
von NEUMANN EXTRACTOR
It is an extractor that keeps taking successive pairs of consecutive bits (non-overlapping)
from the input stream and if the two bits are the same, no output is generated; if they
are different the first of them is outputted.
For example the input sequence
10111100001111000011100110010101
is transformed to the sequence
1101000
The von Neumann extractor can be shown to produce a uniform output, even if the
distribution of the input bits is not uniform, so long as each bit has the same probability
of being one and there is no correlation between successive bits.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 57/58
EXTRACTORS - FORMAL DEFINITION
Definition A (k, ε)-extractor is a mapping
Ext : {0, 1}n
× {0, 1}d
→ {0, 1}m
such that for every distribution X on {0, 1}n
with H∞(X) ≥ k the distribution Ext(X, s)
is ε-close to the uniform distribution on {0, 1}m
.
The aim is to have n > m and d << m.
By a probabilistic method to be discussed later one can show that there exists a (k, ε)
extractor for many k and ε.
Note H∞ stands for so-called min-entropy, which is a measure of the amount of
randomness in the worst case.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 58/58
APPENDIX
KNAPSACK PROBLEM Given n items with weights w1, . . . , wn and values c1, . . . , cn,
as well as a knapsack limit k, find a binary vector (b1, . . . , bn) such that n
i=1 bi wi ≤ k
and n
i=1 bi ci is as large as possible.
VERTEX COVER PROBLEM. Given a graph G, find the smallest set S of nodes such
that each edge of G coincides with at least one vertex of S.
prof. Jozef Gruska IV054 2. Types and basic design methods for randomized algorithms 59/58