# Approximation Algorithms (APX)

### Course content

Many important computational problems are difficult or impossible to solve exactly or optimally. For example,

• many optimization problems are NP-hard,
• some problems have inputs so large that exact algorithms are infeasible, and
• some problems require decisions to be made on-line, based on incomplete information.

Instead, we use approximation algorithms to efficiently find solutions that are provably close in quality to the exact or optimal solutions.

The course covers techniques for designing and analysing approximation algorithms for various computational problems, focusing on optimization algorithms, sublinear algorithms, and on-line algorithms. It is aimed at students who like to use mathematics to design and analyze algorithms.

The topics mentioned under Learning Outcome are covered in lectures and worked on in exercises in order to develop the necessary skills and competences.

Education

MSc Programme in Computer Science

Learning outcome

Knowledge of

• Greedy algorithms
• Rounding data and dynamic programming
• Rounding of linear programs and semidefinite programs
• Streaming algorithms for distinct elements, multisets, and ordered sets
• Competitive analysis for on-line algorithm

Skills in

• Proving approximation guarantees for optimization, streaming, and on-line algorithms
• Using linear programming as a basis for designing approximation algorithms
• Using randomization to design approximation algorithms

Competences to

• Extending approximation algorithms seen in the course to a more general setting, or to related settings.
• Apply approximation algorithms seen in the course to solve new computational problems.
• Communicate effectively about the theory of approximation algorithms, both for accessing advanced topics from the research literature and for convincingly presenting the results of own work.

Lectures and compulsory assignments.

Expected to be:

• The Design of Approximation Algorithms by Shmoys and Williamson.
• Small Summaries for Big Data by Cormode and Yi.
• Various lecture notes or papers.

The students should be comfortable with formal, mathematical reasoning, as the course uses the power of mathematics to understand and prove good performance of algorithms. It is assumed that the students have completed an algorithms course such as Advanced Algorithms and Data Structures, and are comfortable using mathematical proofs in the analysis of algorithms.

Academic qualifications equivalent to a BSc degree is recommended.

Written
Individual
Continuous feedback during the course of the semester
ECTS
7,5 ECTS
Type of assessment
Oral examination, 30 minutes (including grading)
Type of assessment details
The oral examination is with 30 minutes preparation.
Exam registration requirements

The student must solve mandatory assignments during the course. Assignments will be given each week and are due in the following week. 4 out of 6 assignments must be submitted timely and approved in order to qualify for the exam. Some assignments will be solved in groups, other individually.

Aid
All aids allowed
Marking scale
Censorship form
No external censorship
Several internal examiners
Re-exam

The re-exam has the same form as the ordinary exam.

If the student is not yet qualified to participating in the exam, then qualification can be achieved by handing-in the missing/not-approved assignments. These assignments must be submitted no later than three weeks before the week of the re-exam in order to qualify for the re-exam.

##### Criteria for exam assessment

See Learning Outcome.

Single subject courses (day)

• Category
• Hours
• Lectures
• 36
• Preparation
• 85
• Exercises
• 84
• Exam
• 1
• English
• 206

### Kursusinformation

Language
English
Course number
NDAK16001U
ECTS
7,5 ECTS
Programme level
Full Degree Master
Duration

1 block

Placement
Block 4
Schedulegroup
A
Capacity
No limitation – unless you register in the late-registration period (BSc and MSc) or as a credit or single subject student.
Studyboard
Study Board of Mathematics and Computer Science
##### Contracting department
• Department of Computer Science
##### Contracting faculty
• Faculty of Science
##### Course Coordinator
• Srikanth Srinivasan   (4-7877787745696e33707a336970)
Saved on the 25-06-2024

### Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students