Clustering for Set Partitioning: A Case Study in Carpooling

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.