Max-Min Diversification with Asymmetric Distances

One of the most well-known and simplest models for diversity maximization is the Max-Min Diversification (MMD) model, which has been extensively studied in the data mining and database literature. In this paper, we initiate the study of the Asymmetric Max-Min Diversification (AMMD) problem. The input is a positive integer 𝑘 and a complete digraph over 𝑛 vertices, together with a nonnegative distance function over the edges obeying the directed triangle inequality. The objective is to select a set of 𝑘 vertices, which maximizes the smallest pairwise distance between them. AMMD reduces to the well-studied MMD problem in case the distances are symmetric, and has natural applications to query result diversification, web search, and facility location problems. Although the MMD problem admits a simple 1 2 -approximation by greedily selecting the next-furthest point, this strategy fails for AMMD and it remained unclear how to design good approximation algorithms for AMMD.

We propose a combinatorial 1 6𝑘 -approximation algorithm for AMMD by leveraging connections with the Maximum Antichain problem. We discuss several ways of speeding up the algorithm and compare its performance against heuristic baselines on real-life and synthetic datasets.