What do hierarchical clustering, geometric stable matching, and combinatorial optimization problems have in common? In all three areas, there are problems that can be solved effectively using greedy algorithms, and (as we will show in this talk) many of these problems have an underlying combinatorial structure that can be exploited to speed up the runtime of the greedy algorithms. We focus on the use of a specific technique and its application across all three fields: the nearest-neighbor chain algorithm. This technique originated in the context of speeding up hierarchical clustering algorithms in the 80s, and a slight variation was recently used to the same effect in the context of some stable matching problems. Independently, Robert Preis developed a linear-time two-approximation algorithm for the maximum weighted matching problem using similar ideas. In this talk, we work toward unifying all these algorithms into a single framework, and extend the techniques to other problems such as maximum independent set and set cover.
(Joint work with Pedro Matias.)