CSE 421 Assignment #7
Autumn 2012

Due: Wednesday, November 28, 2012.

Reading Assignment: Kleinberg and Tardos Chapter 8

Problems: For all problems on this homework that involve proving NP-completeness, give a full argument that shows that your reduction is correct and runs efficiently and make sure to prove that your problem is in NP also. If you are giving an algorithm, prove that your algorithm is correct and show that it runs efficiently.

1. Suppose you have one machine and a set of n jobs a₁, a₂, ..., a_n to process on that machine. Each job a_j has a processing time t_j, a profit p_j, and a deadline d_j. The machine can process only one job at a time, and job a_j must run uninterruptedly for t_j consecutive time units. If job a_j is completed by its deadline d_j, you receive a profit p_j, but if it is completed after its deadline, you receive a profit of 0. Give an efficient algorithm to find the schedule that obtains the maximum amount of profit, assuming that all processing times are integers between 1 and n. What is the running time of your algorithm?

2. Kleinberg and Tardos, Chapter 7, Problem 19, page 425-426.

3. Kleinberg and Tardos, Chapter 8, Problem 4, pages 506.

4. Kleinberg and Tardos, Chapter 8, Problem 5, pages 506-507.

5. Extra credit: Suppose that you have a set S of possible labels and are given a directed graph G=(V,E) with a designated start node s with each edge (u,v) having a label L(u,v) which is an element of S. (Note that multiple edges out of a node may have the same label.) In addition, each edge has a probablity p(u,v)≥ 0 of being taken when at u. (That is, for every u in V the sum over all v with (u,v) in E of p(u,v) is 1.) The probability of taking a path begining at the start node s is the product of the probabilities labeling its edges. Produce an efficient algorithm that will take as input the graph G with its edge labels and edge probabilities and a sequence of labels a₁ ...,a_t and will determine the most likely path beginning at node s that is consistent with the sequence of labels (and determine the probability of that path). You can assume that arithmetic operations on real numbers have cost 1.