Approximation Algorithms

Abstract

We look into approximation algorithms for computationally hard discrete optimization problems. Their quality is measured by the approximation ratio, i.e., the worst-case ratio between the quality of the computed solution and an optimal one, depending on the input size. We explore different techniques for the design and analysis of approximation algorithms and the limits of this approach.

Objective

To systematically acquire an overview of the methods for the design and analysis of approxmation algorithms. To get deeper knowledge of the classification of optimization problems according to their approximability. To learn how to analyze the approximation ratio of approximation algorithms.To learn about the limits of the approximation approach.

Content

In this seminar, we discuss how approximation can help to compute satisfactory solutions for computationally hard optimization problems. In the kick-off meeting, we will give a brief overview of modeling and classifying approximation algorithms. Then, each participant will study one aspect of this topic, following a specific scientific publication, and will give a presentation about this topic. The topics will include design methods for approximation algorithms like greedy strategies, dynamic programming, or LP-based techniques as well as the classification of optimization problems according to their approximability. The considered problems will be well-known optimization tasks like satisfiability problems, routing problems, packing problems, etc.

Resources