Comparison of the greedy algorithm with the optimal solutions of the Marriage Problem

Applied Discrete Structures 2013-03-15

In Section 9.5, we introduce graph optimization problems, with an emphasis on the Traveling Salesman Problem and the Network Flow Problem. A the end we mention a few others, including the Minimum Matching Problem, also known as the Marriage Problem. I've just posted a demonstration of this problem, comparing the greedy algorithm with the optimal solution. This is an example of a cdf file.