Lecture Summaries for COMP
360
Fall
2013
also check:
announcements
assignments return to:
course home page
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