# Approximation Algorithms ALL SECTIONS (WI22)

## 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.

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

1/19

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.