Find the set of K elements between n that maximize the total distance - Computational Science Stack Exchange most recent 30 from scicomp.stackexchange.com 2022-01-27T02:40:13Z https://scicomp.stackexchange.com/feeds/question/20056 https://creativecommons.org/licenses/by-sa/4.0/rdf https://scicomp.stackexchange.com/q/20056 3 Find the set of K elements between n that maximize the total distance Barbus https://scicomp.stackexchange.com/users/0 2015-07-01T17:08:53Z 2017-02-21T03:18:09Z <p>Given a set $Q$ of $n$ points, we want to find the subset $S_\max \subset Q$ of $k$ elements that maximize the total distance between them.</p> <p>$$S_\max = \max_S \sum_{\substack{ i,j\in S\\ i \neq j}} d(x_i,x_j)$$</p> <p>where in my case $x_i$ is a boolean vector and the distance considered is the Manhattan/Hamming distance.</p> <p>Is there any efficient way to solve this problem? Is it possible to rewrite it in another simpler way?</p> https://scicomp.stackexchange.com/questions/20056/-/24825#24825 1 Answer by D.W. for Find the set of K elements between n that maximize the total distance D.W. https://scicomp.stackexchange.com/users/4274 2016-08-24T23:09:22Z 2016-08-24T23:09:22Z <p>This is known as the farthest-point clustering problem. It is NP-hard, but there is a approximation algorithm: <a href="https://en.wikipedia.org/wiki/Farthest-first_traversal" rel="nofollow">https://en.wikipedia.org/wiki/Farthest-first_traversal</a>. The problem has normally been studied with the Euclidean distance metric, but you can apply the same greedy algorithm to the Hamming distance, too, to get an approximate (but not necessarily optimal) solution.</p>