[MUSIC] Hello and welcome to the coursera course on approximation algorithms. This is a two part course. And I would like to tell you about the first part of this course. These algorithms are for dealing with problems from combinatorial optimization. Combinatorial optimization problems come up all the time in daily life. For example, scheduling classes. You want to schedule classes to avoid overlap when students are sign up for several different classes to make sure that there are always classrooms available for your classes and to take into account various constraints having to do with your school. Or perhaps you own a truck company and you need to plan delivery routes for your trucks. What kind of delivery routes? You need to deliver your goods to all the customers who ask for them, and perhaps you wish to minimize the amount of fuel spent by your trucks. There are many other instances of combinatorial optimization problems. Unfortunately most of them are NP-hard, meaning ST is different from NP. There is no hope for finding an efficient solution in all cases. Polynomial time solution for all instances in the worst case. So, what to do? Dealing with NP-hard problems can be done in several different ways. Number one, give up. This problem is impossible. You cannot hope to find a good solution in reasonable time. All right, this is not an option when you have to deal with real life problems. Option number two, roll up our sleeves. Okay, let's try to look at all possibilities and take the best one. Yes, it will take a long time but let's just be brave and roll up our sleeves. Well unfortunately this is about the same as giving up. Because on many instances as soon as they become a little bit large this will take you forever, and you won't be able to give the best solution. All right. Third option. Perhaps you're just going to try something and hope to be lucky. For example, delivery routes. You'll say okay, let me try to send one truck here, there, there, and there and another truck to another sequence of customers and maybe, maybe your solution will be good. This, for a theoretician, like myself, is not acceptable because you have no control over your solution. This design of heuristics is not the kind of things we are striving for. Fourth solution, let's try to do a rough, but good enough, job. What does it mean? First, we limit ourselves to work in polynomial time. Second, We give up on finding the optimal solution. Instead, we try to find a good enough solution. What does good enough mean? It means there's a certain objective we have in mind, and our goal is to find the solution whose value is not too much worse than the optimal solution. Provably within a small factor of the optimal solution. So how do we go about designing approximation algorithms? First we recognize that real life problems are too complex. This is out of our reach for most real life problems. Instead, what we will do in order to be able to prove things, is study idealized versions of the problems that come up. Idealized version of the knapsack problem, for example,. And then, on these simple idealized problems, with few parameters defining the input. We can hopefully prove theorems. These theorems give us new algorithmic and structural insights on the difficulty of the problems. And so, we start from real-life situations. We distill the difficulties to define basic theoretical primes. On those problems, we do theory we design a solution, an algorithm. We prove some theorems about it. On the route to doing that, we get some new ideas. Then we have to go back to real life and apply that theory to the real life situation. In this course, I will focus on the theory for basic problems. I will not talk about going back and forth between real life and to theory and back to real life. I will be focused solely on the theory of approximation algorithms for basic problems. So what problems are we going to study? The choice of problems is guided by two concerns. One, I want famous problems. Well-studied problems that you would like to know about. It's good for your culture to have heard about these problems. Two, I would like problems each of which gives you an opportunity to learn about techniques for the design of approximation algorithms. In this part of the course, the first part of the course, there are five chapters corresponding to five problems, five different techniques in the design or in the analysis. First, vertex cover. Second, knapsack. Third, bin packing. Fourth, set cover. Five the most difficult problem in this part of the course, the multiway cut problem. So I will start shortly with the first problem in our list, the vertex cover problem. And it will be a chance to introduce one important technique in a design of approximation algorithms, having a linear programming relaxation for the problem. But before I start with the technical part, let me introduce all the staff that is helping with this course. Vincent Cohen-Addad, Frederik Mallmann-Trenn, and Victor Verdugo, the three teaching assistants. Unfortunately, Victor Is here, Vincent is here, but Frederik is not here today. He's out sick, but Vincent and Victor can both introduce themselves. Vincent would you like to say a few words about yourself? >> Sure. Thanks. Hi, I'm Vincent Cohen-Addad. I'm a PhD student here at TNS working on approximation algorithm. I'm very happy to be a teaching assistant for this course airamook. >> Thank you, Vincent. Victor? Would you like to say a few words about yourself? >> Hola, I'm Victor Verdugo. I'm from Chile, and I'm currently working in Paris for my PhD thesis. I'm very glad to be part of this course airamook as teaching assistant. Thank you Victor. Let me also mention, our film director, Naudie and our cameraman, Joe who, unfortunately, are both camera shy. Once again, welcome to the Coursera course on Approximation Algorithms, Part One.
