1. Scheduling with unrelated machines is a generalization of the scheduling problem we discussed. The processing time of job j on machine i is pij, thus it depends on the machine as well. Exercise 11.1 describes a 2- approximation algorithm for minimizing completion time.
This problem is about a simpler 2-approximation algorithm, which is polynomial for a fixed number of machines only. Consider the integer program
min t m
xij = 1, j = 1,…,n i=1
n
pijxij ≤ t, i = 1,…,m j=1
xij ∈ {0,1}, i = 1,…,m, j = 1,…,n a) Explain why this is a reformulation of the original problem.
b) Please read the paragraph on page 279. about basic optimal solutions. Consider the LP relaxation xij ≥ 0, and let x∗ be a basic optimal solution, which thus has at most n + m positive components (the number of constraints). Show that with the exception of at ≤ m − 1 jobs, every job is assigned by x∗ to a single machine.
c) Complete the schedule by finding an optimal schedule of the remaining at most m − 1 jobs by checking all possible schedules. Show that the resulting algorithm is a 2-approximation algorithm, and it is polynomial for every fixed number m of machines.
2. Consider the unweighted set cover problem, where every set has weight 1. a) Give a simplified proof of the O(ln n) bound for the greedy algorithm.
Hint: Let nk be the number of elements that remain uncovered at the start of the kth iteration (thus n1 = n), and let sk be the number of new elements covered in the kth iteration. Show that sk ≥ nk/OPT, and so
1k nk+1≤ 1−OPT ·n.
b) Assume every set has size ≤ d. Show that in this case greedy is a O(ln d) approximation algorithm. Hint: argue as in Problem 2, but only until nk gets below (a lower bound for) OPT.
3. An online graph coloring algorithm receives the graph to be colored vertex by vertex. Each time a new vertex is received, its neighbors among the previous vertices are specified. The algorithm has to color that vertex at that time, without knowing what comes later. For example, the greedy graph coloring algorithm, which assigns to every vertex the first color not assigned to its previously colored neighbors, is an online algorithm.
a) Consider the bipartite graph with vertex sets A = {a1,…,an} and B = {b1,…,bn} and edge set {(ai,bj) : i ≠ j}. Show that for some ordering of the vertices the greedy algorithm will use n colors (instead of 2).
b) Consider a path (a, b, c, d). Show that no online algorithm can guarantee to use 2 colors.
Hint: One can think of this as an “adversary” providing the vertices, depending on the colors chosen by the
algorithm, in a malicious manner, trying to force the algorithm to use many colors.
c) Show that for every k, every online algorithm will use at least k colors for some tree (instead of 2). Hint: argue by induction, based on part b).
1