In classic complexity theory, coping with NP-hard optimization problems often translates to the following fundamental question: “What is the best approximate solution that we can get in polynomial time?” We will present basic techniques for the design and analysis of approximation algorithms.
This includes combinatorial techniques (such as local search and local ratio) and techniques based on linear programming. We will demonstrate the use of these techniques for solving packing and scheduling problems, as well as problems on graphs.
In this class, we will learn how to use Lean to prove mathematical theorems.
The first class will include a short introduction to Lean. In the few following weeks, you will learn the hooks by following slides and solving exercises in groups. The instructors will go from group to group, helping you understand the material. At this point, you will divide into groups, each group choosing a project (a certain theorem or a certain mathematical theory). The rest of the semester will be devoted to completing the project, with help from the instructors.
The topic of the seminar is Algorithms for Sustainable Resource Allocation.
We will review new variants of classic resource allocation problems arising in modern
computing paradigms aimed at sustainable allocation of resources, and the challenges
they present from algorithmic viewpoint. Background material on approximation techniques
for resource allocation problems which are known to be hard to solve will be presented in several
introductory lectures at the beginning of the seminar.