Clustering for Set Partitioning: A Case Study in Carpooling - Wu, Cathy; Kamar, Ece; Horvitz, Eric (In Proceedings of the Workshop on Optimization for Machine Learning (OPT) at NIPS 2015., 2015)
By exploring alternative approaches to combinatorial optimization, we propose the first known formal connection between clustering and set partitioning, with the goal of identifying a subclass of set partitioning problems that can be solved efficiently and with optimality guarantees through a clustering approach. We prove the equivalence between classical centroid clustering problems and a special case of set partitioning called metric k-set partitioning, we discuss k-means and regularized geometric k-medians, and we give several future extensions and applications. Finally, we discuss a case study in combinatorial optimization for carpooling.