Combinatorial Optimization 553.766
TTh 4:30pm - 6:30pm, ONLINE VIA ZOOM
GENERAL INFORMATION
Zoom link : Check Blackboard for passcode protected Zoom link.
Instructor : Amitabh Basu
Office Hours : Wednesday 6:30 -- 8:00pm, email for appointment. Office Hours will be via Zoom. See Blackboard for a passcode protected Zoom link to my virtual office.
Email : basu [dot] amitabh [at] jhu [dot] edu
Teaching Assistant : Ning Liu and Hongyi Jiang will be the TAs for our class.
Ning's email is nliu15 [at] jhu [dot] edu.
Hongyi's email is hjiang32 [at] jhu [dot] edu.
Ning's office hours will be on Thursdays from 7:00 -- 8:00pm. See Blackboard for a passcode protected Zoom link for Ning's virtual office.
Hongyi will not have office hours.
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 two take home Midterms. 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.
Homeworks
- Homeworks will be posted on Blackboard.
Midterms
- The first Midterm will be take home. It will be posted on Blackboard by Friday, February 26, 2021 by noon. It will be due back the following Tuesday, February 2, 2021 at the beginning of class. For the rules governing the test, see the syllabus.
The syllabus for the first midterm will be everything covered up to and including the lecture on Thursday, February 25.
- The second Midterm will be take home. It will be posted on Blackboard by Friday, April 2, 2021 by noon. It will be due back the following Thursday, April 8, 2021 at the beginning of class. For the rules governing the test, see the syllabus.
The syllabus for the second midterm is all the material covered during the course of the semester.
Grades
- 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.