[MUSIC] Where does LP duality come from? Who came up with this idea and in what kind of context do linear programming formulations arise? Let's briefly mention a short history of LP Duality. First, linear programming, linear programming really came to the fore, came to existence, during World War II. World War II logistics were modeled with linear inequalities by Kantorovich solved logistical problems. At the same time Koopsmans also used linear programming to model economic problems. Both of them later shared a Nobel Prize for this contribution. Hitchcock also worked on linear programming for designing a model to solve transportation problems. So all these things have in common logistics or economical problems that came to the fore during World War II. Then, Danzig was a mathematician, George Dantzig, who really did a lot of groundbreaking work on studying linear programming. He's the one who started designing the simplex algorithm, that's still now is one of the most efficient algorithms for solving linear programs in practice. He started by doing some planning for the US Air Force. And as he was discussing his ideas and that new problem, linear programming with von Neumann he mentioned it to him. And von Neumann at the time was working on Game theory and immediately realized, it is said, that he could apply Game Theory duality to this problem and that is how linear programming duality came into being. It was published in 1948 in the paper entitled, A Theorem on Linear Inequalities. But what about using LP duality for approximation algorithms? Although there were some precursors for using LP duality, the most interesting developments really started taking place in the mid 1990s. There was a paper by Agrawal, Klein, and Ravi who designed a solution for this Steiner Forest problem that we will see in the next chapter. And they designed it explicitly relying on linear programming duality. This was perhaps the first example where primal dual algorithms were key to finding the right algorithm for the problem. That was for Steiner Forest. And then almost immediately Goemans and Williamson built on that idea and extended it vastly to produce a collection of problems for which you could use a standard, standard primal dual approach to design good approximation algorithms. Now that caught people's attention, and that was the beginning of an explosion of papers solving LP hard optimization problems using a primal dual approach. So we're going to see, for example, facility location as one of those important problems solved in the late 1990s. And so because of the importance of this method that is why we wanted to spend a little time talking about the mathematical background of linear programming duality.