Combinatorial Optimization 553.766
TTh 3:00pm - 4:15pm, HODSON HALL 315
Instructor : Amitabh Basu
Office Hours : Thursday 4:30 -- 6:30pm, email for appointment. Office Hours will be in my office : Whitehead 202B.
Email : basu [dot] amitabh [at] jhu [dot] edu
Teaching Assistant : Tu Nguyen will be the TA for our class. Tu's email is tnguy177 [at] jhu [dot] edu.
Tu's office hours are on Tuesdays 10am--12noon in Whitehead 212.
Text : No required text, but the following resources are very helpful.
Useful textbooks and resources
- The "4-Bill Book": Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schrijver; 1st edition; ISBN 978-0-471-55894-1.
- 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
- Combinatorial Optimization (3 volumes) by Lex Schrijver; ISBN 3-540-44389-4
- Geometric Algorithms and Combinatorial Optimization by Grotschel, Lovasz, Schrijver; ISBM 978-3-642-78242-8.
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, I will put up HW exercises every week. 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. Solutions to HW I.
- HW for Week II. Solutions to HW II.
Please hand in the following problems in class on Tuesday, February 18, 2020: Problems 4, 5, 9 from HW for Week I and Problems 1, 2, 4, 10 from HW for Week II (7 problems in all are to be handed in).
There was a typo in the statement of Problem 1, part ii. The total capacity of a cut was denoted by u(\delta(R)), instead of c(\delta(R)). This has now been corrected. Thanks to Kyle Gatesman for catching this!
- HW for Week III. Solutions to HW III.
- HW for Week IV. Solutions to HW IV.
Please hand in the following problems in class on Tuesday, March 3, 2020: Problems 2, 4, 5, 9 from HW for Week III and Problems 1, 3 from HW for Week IV.
- HW for Week V. Solutions to HW V.
- HW for Week VI. Solutions to HW VI.
Please hand in the following problems in class on Thursday, April 2, 2020: Problems 1, 2(i), 2(iv), 8 from HW for Week V, and Problems 2, 7, 8 from HW for Week VI.
- HW for Week VII. Solutions to HW VII.
- HW for Week VIII. Solutions to HW VIII.
Please hand in the following problems on Tuesday, April 14, 2020: Problems 2, 5, 7(h), 7(i), 7(n), 8(a), 8(e), 9(d) from HW for Week VII, and Problems 1(i), 1(ii), 1(iii) from HW for Week VIII.
- HW for Week IX. Solutions to HW IX.
- HW for Week X. Solutions to HW X.
Please hand in the following problems on Thursday, April 30, 2020: Problem 2(i) and 3 from HW for Week IX, and Problems 1, 2, 3 (all parts) from HW for Week X.
- The Midterm will be take home. It will be posted here on Friday, March 6, 2020 by noon. It will be due back the following Tuesday, March 10, 2020 at the beginning of class. For the rules governing the test, see the syllabus.
The Midterm is posted HERE. Please read the instructions on the test carefully.
- Final Exam will be
open book take home. It will be in class on Thursday, May 7, 2020, 9am -- 12 noon. It will be posted here on Monday, May 4, 2020 by noon. It will be due on Thursday, May 7, 2020 by 12 noon. For the rules governing the test, see the syllabus.
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.
The Final Exam is posted HERE. Please read the instructions on the test carefully. If you would like the .TEX file to write up your answers in LaTex, please email me.
- Your final grade will be based on the following weightage:
Homework - 35%
Midterm - 30%
Final - 35%
- Blackboard will be used to post the HW and exam grades. You should be able to access your grades there.