[SOUND] Three elements to studying these approximation algorithm problems. The problem, facility location. The technique, primal dual. The people, who are the people who led to these beautiful results? Let's take a few minutes and mention the names of a few of them. Michel Balinski. He's the one who first came up with the linear programming relaxation that we have used in this chapter to study facility location. He was also part of a movement in the operations research community to develop interest in this program led by applications. This is very old. The LP relaxation dates back to 1963. Way before people knew how to solve linear programs really efficiently. David Shmoys, Eva Tardos, Karen Aardal. They are the people who came up with the first constant factor approximation algorithm for facilitated location. It is the four approximation that I presented early on. Actually, in their paper, they prove a 3.16 approximation. Then, I show the different improved algorithm. Jain Vazirani. Kamal Jain, Vijay Vazirani, they are the ones who came up with this very elegant three approximation that does not require you to solve the linear problem explicitly. So this where the pioneers in the design and the knowledges of approximation algorithms for facility location. Now of course on the other side, there was also some work to try to see how hard the problem was. And the current hardness result is due to Samir Khuller and Sudipto Guha. That's his picture from his webpage. Where they show that under some complexity assumption, that I won't detail here, there's a lower bound of 1.463. You cannot hope to have an approximation algorithm with an approximation factor of better than 1.463. And there have been many papers getting various improvements on the basic facility location problem in the metric setting since then. And what is the current best? The current best is quite recent, it's due to Shi Li. He proved a 1.488 approximation in 2011, building on previous work. So there's a whole sequence of papers that I'm skipping. A whole set of people that I am not mentioning. But the current leader is Shi Li, and the current approximation is 1.488. So what does this mean? Best, 1.488. Lower bound, 1.463. There's not that much room between 1.463 and 1.488. At this point, for the version of the problem we've been focusing on, where the costs satisfy the triangular inequality. Where the facilities have no capacity, they can get as many clients as they wish. Well, for this portion of the problem, we're pretty close to the optimal solution. So, now we are more or less done studying facility location as a prime example of use of primal-dual algorithms.