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

Joachim Spoerhase, Kamyar Khodamoradi, Benedikt Riegel, Bruno Ordozgoiti, Aristides Gionis
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:1719-1746, 2023.

Abstract

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$-median, aims to find a set of cluster centers that are not too far from each other, and it has applications, or example, when selecting a committee to deliberate on a controversial topic. This problem was introduced recently (Ordozgoiti et al., 2019), and it was shown that a local-search-based algorithm is always within a factor $O(k)$ of an optimum solution and performs well in practice. In this paper, we demonstrate a close connection of reconciliation $k$-median to a variant of the $k$-facility location problem, in which each potential cluster center has an individual opening cost and we aim at minimizing the sum of client-center distances and the opening costs. This connection enables us to provide a new algorithm for reconciliation $k$-median that yields a constant-factor approximation (independent of $k$). We also provide a sparsification scheme that reduces the number of potential cluster centers to $O(k)$ in order to substantially speed up approximation algorithms. We empirically compare our new algorithms with the previous local-search approach, showing improved performance and stability. In addition, we show how our sparsification approach helps to reduce computation time without significantly compromising the solution quality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-spoerhase23a, title = {A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median}, author = {Spoerhase, Joachim and Khodamoradi, Kamyar and Riegel, Benedikt and Ordozgoiti, Bruno and Gionis, Aristides}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {1719--1746}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/spoerhase23a/spoerhase23a.pdf}, url = {https://proceedings.mlr.press/v206/spoerhase23a.html}, abstract = {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$-median, aims to find a set of cluster centers that are not too far from each other, and it has applications, or example, when selecting a committee to deliberate on a controversial topic. This problem was introduced recently (Ordozgoiti et al., 2019), and it was shown that a local-search-based algorithm is always within a factor $O(k)$ of an optimum solution and performs well in practice. In this paper, we demonstrate a close connection of reconciliation $k$-median to a variant of the $k$-facility location problem, in which each potential cluster center has an individual opening cost and we aim at minimizing the sum of client-center distances and the opening costs. This connection enables us to provide a new algorithm for reconciliation $k$-median that yields a constant-factor approximation (independent of $k$). We also provide a sparsification scheme that reduces the number of potential cluster centers to $O(k)$ in order to substantially speed up approximation algorithms. We empirically compare our new algorithms with the previous local-search approach, showing improved performance and stability. In addition, we show how our sparsification approach helps to reduce computation time without significantly compromising the solution quality.} }
Endnote
%0 Conference Paper %T A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median %A Joachim Spoerhase %A Kamyar Khodamoradi %A Benedikt Riegel %A Bruno Ordozgoiti %A Aristides Gionis %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-spoerhase23a %I PMLR %P 1719--1746 %U https://proceedings.mlr.press/v206/spoerhase23a.html %V 206 %X 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$-median, aims to find a set of cluster centers that are not too far from each other, and it has applications, or example, when selecting a committee to deliberate on a controversial topic. This problem was introduced recently (Ordozgoiti et al., 2019), and it was shown that a local-search-based algorithm is always within a factor $O(k)$ of an optimum solution and performs well in practice. In this paper, we demonstrate a close connection of reconciliation $k$-median to a variant of the $k$-facility location problem, in which each potential cluster center has an individual opening cost and we aim at minimizing the sum of client-center distances and the opening costs. This connection enables us to provide a new algorithm for reconciliation $k$-median that yields a constant-factor approximation (independent of $k$). We also provide a sparsification scheme that reduces the number of potential cluster centers to $O(k)$ in order to substantially speed up approximation algorithms. We empirically compare our new algorithms with the previous local-search approach, showing improved performance and stability. In addition, we show how our sparsification approach helps to reduce computation time without significantly compromising the solution quality.
APA
Spoerhase, J., Khodamoradi, K., Riegel, B., Ordozgoiti, B. & Gionis, A.. (2023). A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:1719-1746 Available from https://proceedings.mlr.press/v206/spoerhase23a.html.

Related Material