Benedikt Riegel

A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median

In the reconciliation $k$-median problem we ask to cluster a set of data points by picking $k$ cluster centers so as to minimize the sum of distances of the data points to their cluster centers plus the sum of pairwise distances between the centers. The problem, which is a variant of classic $k$-med…