Approximation Algorithms ALL SECTIONS (WI22)

Many problems arising in computer science are NP-hard and therefore we do not expect efficient algorithms
for solving them exactly. This has led to the study of approximation algorithms where algorithms are
supposed to run fast but can return approximate solutions. This course provides a broad overview of the
main techniques involved in designing and analyzing such algorithms. It also explore connections between
algorithms and mathematical fields such as algebra, geometry, and probability.

Prerequisites

A first course on algorithms and mathematical maturity to read and write proofs will be assumed.
Dartmouth Courses: COSC 31, COSC 30.

Textbooks and Material

There is no required textbook, but there are two excellent textbooks on the subject.

Approximation Algorithms by Vijay V. Vazirani
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys

We will try to provide some notes of our own.

**Weekly Schedule**
Date	Topic
1/5	Introduction, Steiner Tree
1/7	Greedy Algorithms
1/10	Local Search : Cut Problems
1/12	Non-oblivious Local Search
1/14	Local Search for k-median*
1/18	PTAS for Load Balancing
1/19	PTAS for Load Balancing (contd)
1/21	LP Relaxations
1/24	Rounding for Matchings
1/25 (X-hour)	(maybe, will see how Monday's lecture goes)
1/26	Rounding for Assigning Jobs
1/28	Finish up GAP.
1/31	Randomized Rounding : Set Cover + Independent Set
2/2	CLASS CANCELLED
2/4	Randomized Rounding : Vertex Cover in Bipartite Graphs and Tripartite 3-uniform Hypergraphs
2/7	Randomized Rounding : Chernoff Bounds and Congestion Minimization
2/8 (X-hours)	The Dual LP
2/9	Duality in Approximation Algorithms : Dual Fitting
2/11	Primal-Dual Approximation Algorithms
2/14	Primal Dual Algorithm for Steiner Forest (Handwritten notes) Notes by Finn
2/16	Using the dual to solve LPs approximately
2/18	Solving LPs with many constraints via Ellipsoid method
2/18 - 2/19	Test
2/21	Cut Problems : s,t & Multiway cut
2/23	Cut Problems : Multicut
2/25	Cut Problems : Sparsest Cut
2/28	Semidefinite Programming
3/2	Goemans Williamson Algorithm for Max Cut
3/4	Karger-Motwani-Sudan Algorithm for Coloring
3/7	Musings on hardness

Logistics

Instructor: Deeparnab Chakrabarty (DeepC)
TA: Manuel Stoeckl

Class will be held in Filene (Moore B13) in the 12-slot (MWF, 12:50p - 1:55p, X hour : T 1:20-2:10)

Office Hours

DeepC : Calendly link (Tue, Thu, 5p - 6p, zoom or physical)

Manuel: Calendly Link (Mon 17:00-18:00, Fri 11:20-12:20, Zoom or in person)

Accessibility Needs

Let me know before the end of the second week of the term if you will need a disability-related accommodation or service. In order for accommodations to be authorized, students are required to consult with Student Accessibility Services ("SAS" <student.accessibility.services@dartmouth.edu>; SAS websiteLinks to an external site.; phone: 603-646-9900) and to email me their SAS accommodation form. We will then work together with SAS if accommodations need to be modified based on the online learning environment. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

Wellness

We recognize that the academic environment at Dartmouth is challenging, that our terms are intensive, and that classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including: your undergraduate deanLinks to an external site., Counseling and Human DevelopmentLinks to an external site., and the Student Wellness CenterLinks to an external site.. I encourage you to use these resources and come speak with me to take care of yourself throughout the term.

COVID-19 addendum

While the COVID-19 pandemic has already changed how this course is structured, it has the potential to result in further personal impact which may prevent you from continuing engagement in the class. This may be due to contraction of the disease by you or a loved one, increased familial responsibilities, financial difficulties, or impacts on your mental/emotional health.

I have structured the course so that, hopefully, these disruptions will not prevent you from successfully learning the material.

In the event that you are directly or indirectly impacted by COVID-19 in such a way that will affect your performance in the course, it is imperative that you reach out to me as soon as possible. You may also reach out to your undergraduate Dean if that would make you more comfortable. We cannot assist you if we don’t know there is a problem. Our first priority is your health and security. We will work to put you in touch with appropriate resources to assist you.

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.

To assist with calendar planning and awareness of our diverse religious and spiritual community, the list of holy days for 2020/2021 can be found at https://students.dartmouth.edu/tucker/spiritual-life/about-spiritual-life/holy-day-calendar. The list represents major holy days which may impact accommodation of campus events in general, as well as student course attendance, exams, Commencement and participation in activities 2020-2021. Thank you for your consideration. If you have any questions about these dates or other concerns, please contact Rabbi Daveen Litwin, Dean and Chaplain of the Tucker Center for Spiritual and Ethical Life.