**Class Time:** TuTh 12:30pm - 1:45pm. CSI 2118.

**Overview:** The main paradigm in the course will be the design and analysis of algorithms for combinatorial optimization. We will cover problems that can be solved optimally in polynomial time (matchings, flows, min-cost flows) as well as study problems that are NP-hard, and for which we can develop approximation algorithms. I expect that the students are already familiar with the material from CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.). I will spend the first two weeks covering some topics such as flows and matchings that you may or may not be familiar with from an undergraduate algorithms course.

**Goals:**

- Learning about efficient algorithms for basic problems that are used as building blocks elsewhere. These include matching, flow, min cost flows, primal-dual methods, LP-rounding etc.
- An understanding of the inherent complexity of problems: Polynomial time, NP-completeness, Approximation Algorithms etc. We will spend a large fraction of the semester studying techniques for designing approximation algorithms. Many of these involve fairly mathematical proofs.
- Semi-definite programming

**Course Work:** TBD

**Prerequisites:** CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.).

**Office Hours:** TBD. If you cannot make these hours, please make an appointment to see me at a different time.

**Office Hours:** TBD. If you cannot make these hours, please make an appointment to see me at a different time.

*I will update this page every week during the semester. I
will place all homeworks as well as solutions to homeworks
here. If you have any trouble accessing them, please let me
know.
*

- The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys.
- Approximation Algorithms by Vijay Vazirani.
- Approximation Algorithms for NP--hard problems by Dorit Hochbaum (editor).
- Combinatorial Optimization: Algorithms and Complexity by Christos Papadimitriou and Ken Steiglitz.
- A compendium of NP optimization problems

- TBD

- TBD