Approximation Algorithms

A course on approximation algorithms for NP-hard combinatorial optimization problems: from complexity classification to specific problems — set cover, vertex cover, the \(k\)-center problem, metric problems (the traveling salesman problem, shortest common superstring) — and greedy, local-ratio, and level algorithms with proven approximation guarantees.

Contents

1. Preface. Complexity classes. NP-hard problems
2. Combinatorial optimization: an introduction
3. The set cover problem
4. Metric problems
5. The \(k\)-center problem
6. Shortest common superstring

About this text

This text is based on lecture notes from seminar sessions.

Author: M.A. Nedoshivin
Email: nedoshivin.ma@phystech.edu

Found a typo or an error? Email the address above.

The materials are distributed under the CC BY-NC-SA 4.0 license; see the “About the project” page for details.