**Text:
***Algorithm Design, *J. Kleinberg and E. Tardos,*
Pearson 2006.
*For the linear programming lectures, the text Linear Programming
(excerpted below) by Vasek Chvatal is recommended

Both texts on reserve at the Schulich Library

Slides:
Please visit the news section of COMP360 in * myCourses*
for the URL of the hidden
folder

Sept 3: Kick off !

Sept 5 : Review of network flows and cuts. Review the slides 07maxflow (first 26), 07demo-maxflow, and read text Ch. 7.1 and 7.2

Exercises: Text Ch 7, Ex 3 and Ex 14.

Sep 10: Circulations and Lower bounds on capacities. Problem reductions. Applications to survey design and open-pit mining. Review slides 07maxflow-applications slides 1-32. (Slides 1-21 are review material).The open pit problem is contained in the first 7 slides of Conor's proposal.

Exercise: Text Ch 7, Ex 28(a)(b). Also construct two small examples for each of (a) and (b) illustrating when a schedule is possible and when it is not.

Sep 12: More flow/cut applications: Image segmentation, k-regular matching and census tabulation. See slides 07maxflow-applications.

We looked at a local improvement algorithm(LIA) to compute the shortest path tree as an alternative to Disjkstra's algorithm. Review slides 04-demo-dijkstra. In the final slide we called the directed tree defined by blue edges the shortest path tree. It gives the shortest path from s to every other node in the graph. To compute this tree by local improvement. Let c_vw > 0 be the input weight assigned to edge vw.

1. Take any directed spanning tree T rooted at s.((Eg. use breadth first search from s.)

2. For each vertex v compute d(v), the distance from s to v in T.

For each edge vw not in T see if d(v)+c_vw < d(w). If no such edge exists stop.

If you find such an edge, delete the edge in T that enters w and add vw to T. Go to 2.

Exercise:

(a) Use LIA to compute the shortest path tree for the example in 04-demo-dijkstra. (Do not start with the shortest path tree in Step 1 !)

(b) Prove that LIA always terminates, and that the tree on termination is a shortest path tree.

Sep 17: Introduction to linear programming. Formulation of wine blending problem and dual. Three outcomes of linear programming. Geometric interpretation. Read: Komei Fukuda's notes pp 1-14.

Exercises:

Figure out the coordinates for each vertex in the figure on p. 10 of the notes. (We did most in class)

Now for each vertex find an objective function for which the vertex is the unique optimum solution. Try to give a proof of optimality by giving an argument as described in Section 2.1.

Eg. For the vertex (2,1,3) an objective function maximizing here is z= 3x1 + 4x2 + 2x3 and the proof of optimality is by the row multipliers 4/3, 1/3, 4/3.

Note you may need to use negative coefficients in the objective function, but this is quite OK.

Sep 19: Linear programming and the simplex method. This is an important lecture as many coming lectures will build on it. It is essential to understand the reading material LP_en.pdf and notes DO THIS EXERCISE!!

Exercise: Write down your own LP with two constraints and four variables (or more!) and solve it by hand according to the method in today's lecture.

Assignment 1: Exercises from lectures on Sept 5,10,12,17,19 due in class on Sep 24 !

Sep 24: How to get an initial feasible solution. Two phase simplex method. General statement of the simplex method. Getting a feasible starting solution. Cycling example. Read LP2_en.pdf (pp 39-43) and notes

Exercise: From LP2_en.pdf do exercise 3.9 on p. 44, all three parts.

Sep 26: Cycling in the simplex method and ways to get around it, see notes pp4-7 and LP2_en.pdf pp29-33 . Worst case of the simplex method: Klee-Minty examples, see slides 22-28 here.

Exercise: Review Bland's least subscript rule given at the end of the notes and on p. 37 of LP2_en.pdf.

Apply this pivot rule to the cycling example on pp 31,32 of LP2_en.pdf

(a)Which is the first dictionary where a different choice would be made?

(b) Find the optimum solution by applying Bland's rule to the dictionary in (a) (just two pivots are required !). Check with lp_solve.

Oct 1: Polynomial Reductions. Text Section 8.1 - 8.2 (including the reduction from 3-SAT to Ind Set).

Exercise: Text Ch. 8, p. 505, Ex 1

Oct 3: NP, NP-completeness, (Statement of) Cook's Theorem. Text Sections 8.3-8.4

Exercise: Text Ch. 8, p. 505, Ex 3

Oct 8: Graph Colouring, co-NP, Good Characterisations, Partial Taxonomy of Hard Problems. Text sections Sec 8.7 and Secs 8.9-8.10.

Exercise: Text Ch. 8, p. 506, Ex 4,5

Oct 10: Tutorial in class and problem session. Please send suggestions to Liana , liana.yepremyan at mail.mcgill.ca

Oct 15: Connections between NP-complete, NP-hard and integer linear programs. Reduction of 3-SAT to SUBSET SUM (see slides 35-37 of slides 08reductions-poly.ppt )

Exercise: The 4-sat problem is the same as 3-SAT except each clause has exactly 4 literals. Modify the reduction done in class and in the slides to directly reduce 4-SAT to SUBSET SUM, and prove its correctness. Illustrate on and example with 3 variables and 3 or 4 clauses.

Oct 17: Two definitions of reducibility Cook vs Karp ( 08np-complete.ppt slides 15,16).

Pseudo-polynomial algorithm for Knapsack problem ( 06dynamic-programming.ppt slides 25-29 ).

Reduction of SUBSET SUM to PARTITION to {Knapsack, 2 machine scheduling}

No Exercise, but I recommend you study carefully the text pp 451-473, 485-490 and relevant slides from 08np-complete.ppt and 08reductions-poly.ppt

Oct 22: Review session in class: Network flows and Linear Programming

Oct 23: Tutorials 10:30-11:30 and 2-3pm McConnell 320 NP-completeness

Notes from Oct 10 tutorial can be found at Tutorials and help

Oct 24: Midterm exam. During class time. Solutions are here.

Covers all material up to and including Oct 17 lecture. At least half of the exam is based closely on the exercises.

Oct 29: Duality. How to construct a dual. The interpretation of dual variables. Adding new variables and changing the right hand side b-vector. Using lp_solve.

Read the first 3 pages of these notes and Chapters 2 and 3 of Fukuda's notes (we will do the duality theorems on Oct 31) . Sample lp_solve files are here. Instructions for lp_solve are here.

Exercise: Using lp_solve do exercise 3.2 of Fukuda's notes (p. 23 of the pdf file). Can you answer any of the questions by just using the optimum dual variables?

(Get them by using : lp_solve -S4 input_file )

Oct 31: The weak and strong duality theorems. We proved the weak duality theorem and saw how to get the optimum dual variables from the final dictionary. Then we discussed how to deal with NP-hard problems, including a backtracking algorithm for SAT (see slides 42-71).

Start reading this chapter from Algorithms, by S. Dasgupta, C. Papadimitriou and U. Vazirani.

Exercise: Do exercise 9.1, p. 306 of the chapter from Algorithms. Hint: Show that if you make a branch step from a node and resolve all the clauses containing that variable, then the resulting formula is satisfiable if and only if the original one was. Conclude that you do not need to follow the other branch from the original node.

Nov 5: The hamilton cycle(HC), directed hamilton cycle(DHC) and travelling salesman problems(TSP). Study the reductions 3SAT <= DHC <= HC <= TSP (decision version)

given in the slides 08reductions-poly. A branch and bound (B & B) algorithm for TSP is in the chapter from Algorithms.

Exercise: (a) Look at the example in Figure 9.2 of the chapter. Compute a lower bound on the root node A of the tree. How does this affect the B & B calculation?

(b) Change the weight on edge EF to 5. Now compute the minimum length TSP using B & B.

Nov 7: Branch and Bound for Knapsack and Integer Programming. notes

Exercise: (a) For the example in the notes consider choosing problem E rather than B at iteration 2. Now draw out the resulting B&B tree. Use no initial feasible integer solution.

(b) How would the tree in (a) look if you started with the initial feasible solution x_1=1, x_4=1, z=30?

Assignment 3: Exercises from lectures on Oct 15,29,31 Nov 5,7 due Nov 12 in class !

Please take time to do the online course evaluation !

Nov 12: Approximation algorithms: machine scheduling aka load balancing. Text section 11.1, slides 11-approx-alg. We got tighter bounds. See Chvatal's notes (which I typed myself !)

Exercise: Text p. 651 problem 1

Nov 14: Approximation algorithms for vertex cover based on matching and linear programming. Read text Section 11.6, chapter Section 9.2.1 and slides 11-approx-alg Section 11.6.

Exercise: Draw a non-bipartite graph on 6 vertices with 7 edges with no perfect matching. Write down the integer linear programs for the maximum matching and minimum vertex cover problems and the LP relaxations. Find the maximum matching, min vertex cover and solve the LP relaxations either by inspection or by using lp_solve. Also compute the rounded solution from the vertex cover LP. Verify that the size of :

maximum matching <= max fractional matching = min fractional vertex cover <= min vertex cover <= rounded vertex cover <= 2 * min vertex cover

Nov 19: Vertex covers for small cover size. A PTAS for the knapsack problem. Text Section 10.1 and 11.8, slides 10extending, 11approx_alg

Exercise: The vertex cover algorithm in section 10.1 relies on the fact that for any edge uv, at least one of u or v must be in a minimum vertex cover. Show that a similar result does not apply to independent set : ie, find a graph and edge uv such that neither u nor v is in the maximum independent set. Use this or similar example to show that the algorithm in Section 10.1 does not adapt to finding an independent set of size k.

Nov 21: Reduction from Hamilton Cycle (HC) to Travelling Salesman Problem (TSP) and why there is no general bound on approximation algorithms for TSP. With the triangle inequality we derived a ratio bound of 2 for the spanning tree heuristic and 3/2 for the spanning tree + matching heuristic (see wiki ). Read the chapter Section 9.2.3 and 9.3.

In section 9.2.3 a Rudrata path is another name for a Hamiltonian path, ie. a path that visits every vertex exactly one.

(The travelling salesman page is here. This material is not required for the exam.)

Exercise: Let G=(V,E) be any connected graph with n=|V|. Construct a TSP on n cities as follows. The weight w_ij is the the number of edges in a shortest path in G between i and j. Show that the bounds on the two heuristics studied today apply to this TSP.

Assignment 4: Exercises from Nov 12,14,19,21. If you wish to have this graded please hand it in on Nov 26. Solutions on Liana's page.

Nov 26: Rewind and rerun: 1

Nov 28: Rewind and rerun: 2

Tutorial:

Dec 3: As this follows Monday schedule, some students have
classes and the tutorial is cancelled.

Dec 4: 11:30-1pm, McConnell 103.
Assignment 4,5 and midterm