Combinatorial Optimization 550.666
TTh 4:30pm - 5:45pm, WHITEHEAD 304
Instructor : Amitabh Basu
Office Hours : Monday 4-6pm, email for appointment. Office Hours will be in my office : Whitehead 202A.
Email : basu [dot] amitabh [at] jhu [dot] edu
Teaching Assistant : Joe Paat will be the TA for our class. Joe's email is jpaat1 [at] jhu [dot] edu.
Joe's office hours are on Wednesdays, 6-8 pm in Whitehead 212.
Text : Required - Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schrijver; 1st edition; ISBN 978-0-471-55894-1.
Other useful textbooks and resources
- Notes on Combinatorial Optimization by Lex Schrijver
- Integer Programming by Conforti, Cornuejols, Zambelli; ISBN 978-3-319-11007-3. Online access by Springer.
- Theory of Linear and Integer Programming by Lex Schrijver; 1st edition; ISBN 978-0-471-98232-6
Syllabus : The syllabus with list of topics to be covered is available HERE.
The main goal of this course is to introduce students to combinatorial optimization techniques. The first part of the course will focus on combinatorial algorithms for classical problems. The next part of the course will show how polyehdral theory can be used to deal with combinatorial optimization problems in a unifying manner.
Schedule : A rough schedule is available here.
EXAM AND GRADING INFORMATION
There will one take home Midterm and an in-class 3 hour Final exam. In addition, there will be regular (approx. weekly) homework assigments. You will be asked to hand in some of the HW problems which will be graded (approximately every two weeks). Seriously attempting ALL the homework problems is imperative for your success in the class, and they will give an indication of the kind of problems on the tests.
Midterms and Final
- HW for Week I/II. Solutions to HW I/II.
- HW for Week III. Solutions to HW III.
Please hand in the following problems in class on Thursday, September 17, 2015: Problems 5,7,8 from HW for Week I/II and Problems 2,6,9 from HW for Week III (6 problems in all are to be handed in).
- HW for Week IV. Solutions to HW IV.
- HW for Week V. Solutions to HW V.
Please hand in the following problems in class on Thursday, October 1, 2015: Problems 4,8 from HW for Week IV and Problems 6, 7(i), 8(i) from HW for Week V (5 problems in all are to be handed in). If you use the result of a HW problem that was not handed in for grading, you must include a proof of that problem.
- HW for Week VI. Solutions to HW VI.
- HW for Week VII. Solutions to HW VII.
Please hand in the following problems in class on Tuesday, October 20, 2015: Problems 1, 7, 8 from HW for Week VI, and Problem 3 from HW for Week VII.
- HW for Week VIII. Solutions to HW VIII.
- HW for Week IX. Solutions to HW IX.
- No HW for Week X.
- HW for Week XI. Solutions to HW XI
- HW for Week XII. Solutions to HW XII.
Please hand in the following problems on Thursday, December 3, 2015: Problem 3 from HW for Week IX, Problems 1, 5 from HW for Week XI, Problems 1, 3 from HW for Week XII.
- The Midterm will be take home. It will be posted here on Friday, October 23, 2015 by noon. It will be due back the following Tuesday, October 27, 2015 at the beginning of class.
The Midterm is posted HERE. Please read the instructions on the test carefully.
- Final Exam will be open book. It will be in class on Thursday, December 10, 2015 from 2-5pm.
The syllabus for the final is all the material covered during the course of the semester. It will have equal weight on the parts covered before the midterm, and the parts covered after the midterm.
- Your final grade will be based on the following weightage :
Homework - 30%
Midterm - 30%
Final - 40%
- Blackboard will be used to post the HW and exam grades. You should be able to access your grades there.