Overview:
● Approximation Algorithms
○ Maximum Cut
○ Minimum Makespan Scheduling
● Computational Complexity
○ Interval Scheduling
○ Zero Weighted Cycle
○ Independent Set
MAX-CUT:
A Max-Cut of an undirected graph G = (V, E) is defined as a cut C_max such that
the number of edges crossing the cut is the maximum possible among all cuts.
Consider the following algorithm.
V
A B
Practice Problems #1 MAX-CUT:
1. Start with an arbitrary cut C(A,B).
2. Let v be an arbitrary vertex, which is either in A or B. Let’s assume that v has some
edges to vertices that crosses the C(A,B), and some edges to vertices that don’t cross
the C(A,B).
3. Pick any v, if it has more edges to vertices that don’t cross the cut, switch the side of v.
4. Repeat until no improvement can be made.
Practice Problems #1 MAX-CUT:
x
z
u v
t
y
What’s the max cut of this graph?
z t
x y
u v
A
B
Max C(A,B) = 8
Tight Example:
MAX-CUT:
A
B
One possible outcome of our algorithm =
cut(A,B) = 2 ( 2 edges crossing the cut and we
can’t improve further).
A B
Optimal Cut = 4
a). Does the algorithm terminate in polynomial time?
MAX-CUT:
First, clearly every time we make a switch, the number of edges crossing the cut
increases by at least 1.
Second, we know that the size of the maximum cut is at most |E|.
Therefore, the algorithm terminates in polynomial time.
b). Prove that the algorithm is a 2-approximation, that is the number of
edges crossing our C is at least half the number of edge crossing C_max.
HINT: what can you infer about each vertex when the algorithm terminates?
MAX-CUT:
– Let be the total number of edges of any vertex v.
– Let be the number of edges of v not crossing the cut
– Let be the number of edges of v crossing the cut.
– Hence,
– After the algo terminates, for every v, (1) – otherwise, we can still move v
and the algo will not terminate yet.
– 2|E| = ← each edge is considered twice for each endpoint vertex.
– From (1) we have that , 2|E| = =
MAX-CUT:
b). Prove that the algorithm is a 2-approximation, that is the number of
edges crossing our C is at least half the number of edge crossing C_max.
b). Prove that the algorithm is a 2-approximation, that is the number of
edges crossing our C is at least half the number of edge crossing C_max.
– From (1) we have that , 2|E| = =
– So |C_max| |E|
– Note that in , we count every cut edge twice, once for each endpoint vertex.
– so,
– Thus, our algorithm is:
– In other words, the number of edges in our cut is at least
MAX-CUT:
Minimum Makespan Scheduling
Suppose we have 1,…,n jobs each of which take time ti,…,tn to process, and m
identical machines on which we schedule the jobs. Jobs cannot be split between
machine. For a given scheduling, let Aj be the set of jobs assigned to machine j.
Let be the load of machine j or total processing time of machine j.
The problem asks for an assignment of jobs to machines that minimizes the
makespan, the maximum load over all machines (i.e., the completion time).
Minimum Makespan Scheduling
1. Order the n jobs arbitrarily
2. Schedule every time the next job on machine that has been assigned least
work so far (i.e., machine which finishes earliest with the jobs assigned to it
so far)
Consider the following algorithm:
Quick Example:
3 jobs p1 = p2 = 1, p3 =2 to be scheduled on 2 machines. Assume we use this order that the
input comes in.
Our algorithm will:
1. assign p1 to M1
2. assign p2 to M2
3. assign p3 to M1 or M2.
The makespan of this schedule is 3.
However, the optimal solution should get a makespan of 2.
Minimum Makespan Scheduling
Proof that the algorithm is a 2-approximation:
Minimum Makespan Scheduling
Let L* be the optimal makespan (maximum completion time).
We have that: → Since every job has to be completed.
The optimal solution is at least as big as the job with the maximum completion time.
We also have that: for another lower bound.
→ the optimal makespan, i.e., the maximum load, should be at least the average
load (best possible way is to divide the total completion time evenly among m
machines.)
Proof that the algorithm is a 2-approximation:
Minimum Makespan Scheduling
Let’s consider machine with maximum load . (i.e., our solution is bounded by this
machine’s total time). Let i be the last job scheduled on this machine.
Now from our algo, when i was scheduled, the machine had the smallest load. In other words,
other machines were still busy at the start time of job i.
We have that: The latest starting time possible of job i If all
machines would take equally long in processing
the first i-1 jobs. If they don’t take equally long,
then some machine becomes available already
earlier for the starting job i.
Clearly,
+
Hence
← From before
This proves that the algorithm is a 2-approximation algorithm.
NP Problems: Interval Scheduling
For each of the two questions below, decide whether the answer is (i) “Yes,” (ii) “No,” or (iii)
“Unknown, because it would resolve the question of whether P = NP.” Give a brief explanation of
your answer.
1. (a) Let’s define the decision version of the Interval Scheduling Problem from Chapter 4 as follows:
Given a collection of intervals on a time-line, and a bound k, does the collection contain a subset of
nonoverlapping intervals of size at least k? Question: Is it the case that Interval Scheduling ≤ P
Vertex Cover?
2. (b) Question: Is it the case that Independent Set ≤ P Interval Scheduling?
NP Problems: Interval Scheduling
NP Problems: Interval Scheduling
NP Problems: Zero Weighted Cycle
You are given a directed graph G=(V,E) with weights we on its edges e∈E. The
weights can be negative or positive. The Zero-Weight-Cycle Problem is to decide if
there is a simple cycle (a cycle with no repeated vertices) in G so that the sum of
the edge weights on this cycle is exactly 0. Prove that this problem is NP-complete.
NP Problems: Zero Weight Cycle
NP Problems: Zero Weight Cycle
NP Problems: Independent Set
Suppose that someone gives you a black-box algorithm A that takes an
undirected graph G = (V, E), and a number k, and behaves as follows.
– If G is not connected, it simply returns “G is not connected.”
– If G is connected and has an independent set of size at least k, it returns “yes.”
– If G is connected and does not have an independent set of size at least k, it
returns “no.”
Suppose that the algorithm A runs in time polynomial in the size of G and k.
Show how, using calls to A, you could then solve the Independent Set Problem in
polynomial time: Given an arbitrary undirected graph G, and a number k, does G
contain an independent set of size at least k?
NP Problems: Independent Set
NP Problems: Independent Set