Maximizing Diversity in (Near-)Median String Selection

We start by considering the problem of finding just two (approximate) medians that are as diverse as possible. In the literature, the maximum Hamming distance between two candidate solutions is referred to as the diameter. When focusing on exact medians (i.e., where the solutions are required to be exact medians), it is relatively straightforward to optimally solve the diameter variant. Specifically, we can efficiently find two Hamming medians that are maximally diverse (see the full version) – thanks to the special structure of the space of Hamming medians. However, this same structure often leads to the Hamming median being unique, which precludes the possibility of constructing a diverse set of exact Hamming medians, even of size two.

In many practical settings, it is sufficient to work with near-medians (i.e., $(1+\epsilon )$-approximate medians for some small $\epsilon >0$). Consequently, when the aim is to generate diverse solutions and diversity is prioritized over optimality of the underlying solutions, a natural question arises: can we find two approximate medians that are as diverse as possible? We answer this question in the affirmative by presenting an efficient algorithm that optimally solves the diameter problem for approximate Hamming medians.

Next, we turn our attention to the task of finding multiple – potentially more than two – (approximate) medians that maximize specific diversity measures. As mentioned earlier, one widely used diversity measure is the sum dispersion, where the objective is to maximize the sum of pairwise Hamming distances among the selected solutions. When generating multiple Hamming (exact) medians, it is still feasible – though somewhat more intricate than the diameter variant – to achieve the maximum sum dispersion (see Theorem 9).

The challenge increases when the goal is to compute a diverse set of approximate medians. For approximate medians, we provide a PTAS for the sum dispersion objective.

The problem becomes more challenging when it comes to min dispersion. The goal here is to produce $k$ (approximate) Hamming median strings that maximize the minimum pairwise distance. In contrast to diameter and sum dispersion, this task is computationally more challenging even when seeking exact medians.

In this paper, we provide an efficient algorithm to generate $k$ Hamming medians while approximating the maximum min dispersion. First, we note that when $k=O(1)$, the problem can be solved optimally using standard dynamic programming in polynomial time. So from now, we assume $k=\mathrm{\Omega }(1)$. We show the following result, a formal statement of which appears in Section 5.

Next, we consider the min dispersion problem over approximate medians. In this case, we provide a bi-criteria algorithm. In particular, we present the following result, a formal statement of which appears in Section 5.

Note that only in the second point of the above result, we attain a bi-criteria approximation. We would also like to highlight that if $t^{\ast }\ge \mathrm{\Omega }\left(\frac{1}{\delta }\sqrt{d}\log k\right)$, we can even get a better bi-criteria bound; more specifically, we output a set of $(1+\epsilon +\delta )$-approximate medians with $(1/2-\delta )$-approximation to the min dispersion objective, for any $\delta >0$.

When optimization involves multiple criteria, there may not be a single solution that is optimal for all objectives. In this context, Pareto-optimal solutions have been studied: these are solutions where no objective can be improved without worsening another. Research has focused on computing approximate Pareto fronts. In particular, [28] shows that for any multicriteria optimization problem, there exists a polynomial-size set of Pareto-optimal solutions such that each objective is satisfied up to a factor of $(1+\epsilon )$, and this set can be computed in polynomial time provided a gap version of the problem can be solved. Further, [21, 22] show that for a class of problems in which a dual exists for a restricted version of a budget-constrained optimization problem, if the dual can be solved in polynomial time, it is possible to obtain $(1+\epsilon )$-approximations for all objectives except one, which can be optimized exactly.

Suppose we are given a dataset $X\subseteq {\mathrm{\Gamma }}^d$, and let $w$ be a Hamming median of $X$. By a simple observation (Lemma 5), for every index $i$, the character $w_i$ at that position in a Hamming median must be one of the most frequent characters at index $i$ in the dataset $X$. Therefore, if there are two distinct Hamming medians, they can only differ at those positions where multiple characters are tied for the highest frequency. This observation facilitates the construction of the two most diverse Hamming medians: for each such index, select two different most frequent characters and assign them to these positions in each median, thereby creating two distinct medians.

The scenario becomes less straightforward when the goal is to generate $k$ Hamming medians that maximize the sum of all pairwise Hamming distances (i.e., maximize sum dispersion). Still, the problem remains quite manageable. Since the objective is to maximize the sum, we can focus on optimizing it coordinate-wise. As before, the only indices that contribute to the sum dispersion among Hamming medians are those with multiple most frequent characters. More specifically, for any such index $i$, suppose there are $r$ most frequent characters, say $a_1,a_2,\mathrm{\cdots },a_r$. Then, the sum dispersion at that index is maximized if each character $a_j$ appears exactly $k/r$ times among the $k$ median strings (assuming $r$ divides $k$; otherwise, the frequencies should be distributed as evenly as possible). It is again easy to generate $k$ Hamming medians that respect the above property, leading to a maximum sum dispersion. We refer to the full version for the details.

The problem becomes much more difficult when it comes to maximizing the min dispersion, i.e., we want to generate $k$ Hamming medians that maximize the minimum pairwise Hamming distances. The computational hardness arises from its innate connection with the minimum distance problem, one of the fundamental questions in error-correcting codes. We begin by giving a dynamic programming algorithm to solve the problem exactly when $k=O(1)$. Thus, from now on, we assume that $k\ge \mathrm{\Omega }(1)$. Next, we consider the following two cases separately: (I) diameter is $\mathrm{\Omega }(\log k)$, and (II) diameter is $O(\log k)$.

For Case (I), we achieve a $(1-\delta )$-approximation to the min dispersion (note, for brevity, we hide the dependency on $1/{\delta }^2$ in the above $\mathrm{\Omega }(\cdot )$ and $O(\cdot )$ notation). Recall that Hamming median requires each index to take only one of the most frequent characters at that index in the input set. Thus, we first compute the set of most frequent characters for each index, denoted as ${\mathrm{\Gamma }}_i$ for index $i$ (${\mathrm{\Gamma }}_i$ may contain a single element). Next, we construct a set of $k$ Hamming medians as follows: For each index $i$, we select a character from ${\mathrm{\Gamma }}_i$ independently and uniformly at random. We repeat this process to generate $k$ strings. To argue that this yields a $(1-\delta )$-approximation to the min dispersion with high probability, we first apply standard concentration bounds to get a lower bound on the min dispersion of the output set. Then we establish a generalized version of the Plotkin bound for codes with potentially different alphabets in each index. Finally, by combining the lower bound on the min dispersion of the output set and the generalized Plotkin bound, we get our desired approximation guarantee. For Case (II), we observe that the set of all candidate Hamming medians is polynomially bounded, and we then apply the classical greedy algorithm for min dispersion from [32], albeit paying a $1/2$-approximation to the min dispersion objective. We refer to the full version for the details.

Due to its special structure, the Hamming median is often unique for an input set, particularly when there is a unique majority character at each position. This uniqueness limits the possibility of having multiple diverse medians. However, this restriction does not generally apply to approximate medians, even if we consider an approximation factor of $(1+\epsilon )$, for any small $\epsilon >0$. For instance, consider an input set $X$ containing $n$ binary strings each of length $d$ such that for every index, the most frequent character is 1 and it occurs in $n/2+1$ strings (i.e., frequency is $n/2+1$). Here, the Hamming median is unique (the all-one string). However, it is easy to observe that even if we consider the all-zero string ($0^d$), it is still an $(1+\epsilon )$-approximate median, for $\epsilon \approx 8/n$, and thus the maximum distance between two $(1+\epsilon )$-approximate medians (referred to as diameter) could be as large as $d$.

In this paper, we present an exact algorithm for this diameter variant. Specifically, we design an algorithm that constructs two $(1+\epsilon )$-approximate medians that are maximally distant from each other. Our approach begins with the string formed by taking the most frequent (majority) character at each position (breaking ties arbitrarily). For each coordinate, we then consider the second most frequent character and assign a weight corresponding to the increase in the median objective if it were chosen instead; this weight is the frequency difference between the most and second most frequent characters. Next, we use a greedy strategy to select a maximal subset $T$ of positions so that the sum of these weights does not exceed $2\epsilon \text{opt}$, where opt denotes the minimum Hamming median objective. Next, we partition this set $T$ in a balanced manner – as evenly as possible into two subsets, $T_1$ and $T_2$, so that the difference in their total weights is minimized. We then output two strings: $z$, which uses the second most frequent characters at indices in $T_1$ and the most frequent elsewhere; and $y$, which uses the second most frequent characters at indices in $T_2$ and the most frequent elsewhere. Intuitively, both $y$ and $z$ have a median objective cost of at most $(1+\epsilon )\text{opt}$ (due to the balanced partitioning), and since $T_1$ and $T_2$ are disjoint, they are maximally apart. To ensure both $y$ and $z$ are $(1+\epsilon )$-approximate medians and they realize the maximum diameter (not even off by a small factor), we introduce some additional refinements in the above selection process, leading to a more intricate analysis, which is detailed in the full version.

Next, we turn our attention to generating $k$ (more than two) $(1+\epsilon )$-approximate medians with the aim of maximizing the sum dispersion measure, denoted as sumDp. This introduces new challenges, particularly in adapting and extending the previous approach used for the diameter variant in the case of approximate medians and for maximizing sum dispersion with exact medians. In the case of the diameter, since only two strings are produced, it is sufficient to focus on the two most frequent characters at each position. However, for generating $k$ approximate medians, we may need to consider more than two characters for each index – potentially all characters in $\mathrm{\Gamma }$ – each associated with a different weight. Recall that the weight of a character at a particular index corresponds to the increase in the median objective if it is selected over the most frequent character.

Furthermore, it is no longer enough to simply identify a set of index positions where replacing the most frequent symbol with another does not increase the median cost by more than $k\epsilon \text{opt}$, and then “distribute equitably” these positions among the $k$ candidate median strings. First, achieving a balanced partition into $k$ groups is hard, especially since $k$ can be arbitrarily large. Second, and perhaps more importantly, even if such a balanced partitioning is efficiently done and we then make changes to the assigned index set for each of the $k$ candidate medians, this does not guarantee maximization of sumDp. For exact medians, we have already observed that maximizing sumDp coordinate-wise requires using as many distinct symbols as possible, distributed as evenly as possible across the candidate median strings. Now, since each symbol at a given position has potentially different weight, we face a trade-off: whether to increase the number of indices where candidates deviate from the most frequent symbol (thus different from the exact median) or to maximize diversity at certain index positions. In essence, the problem now involves meeting $k$ separate “hard” budget constraints (each having a budget of at most $\epsilon \text{opt}$), while still striving to maximize the overall sumDp objective.

To address the challenges outlined above, we first present a $(1-4/D^{\ast })$-approximation algorithm, where $D^{\ast }$ represents the optimal diameter for $(1+\epsilon )$-approximate medians in the given input set. For any $\delta >0$, our algorithm directly yields a $(1-\delta )$-approximation whenever $D^{\ast }>4/\delta$. Otherwise, it is not hard to observe that there are only a polynomial number of possible candidates for the $(1+\epsilon )$-approximate median strings. We argue that the Hamming metric is of “negative-type” and that the constraint of selecting $k$ strings reduces to a matroid constraint. Then, by applying the result from [8] (which essentially involves rounding a quadratic program), we obtain a PTAS. Next, we briefly outline the main ideas behind the $(1-4/D^{\ast })$-approximation algorithm.

We begin with a set $S$ of $k$ identical exact median strings, all equal to $w$; we call $S$ the set of candidate medians. We then consider a collection of modification operations. Each operation is specified by: an index position $i$, a character $a\in \mathrm{\Gamma }$, an integer $r$ – the target frequency of $a$ at position $i$, and an integer $\mathrm{\ell }$ – the frequency of the character $w_i$ at position $i$ among the candidate medians in $S$. We assign each operation a density, which informally measures the ratio between its increase in the sumDp objective and its increase in the median objective if applied.

Next, we sort all plausible operations in nondecreasing order of density and attempt to apply the longest prefix of this sorted list that yields a feasible solution. A prefix is feasible if the following holds: we initially allocate a budget of $\epsilon \text{opt}$ to each candidate median in $S$. Then, for each index $i$ and character $a$, we perform all the corresponding operations in the chosen prefix, one by one, on candidate medians that still have positive remaining budget. After each operation, we deduct the appropriate amount from the budget of the candidate median to whom it was applied. If every operation in the prefix can be completed without any candidate median exceeding its budget, the prefix is deemed feasible. In the algorithm, we execute the selected operations in a carefully chosen order and select which candidate medians to modify so as to guarantee the desired approximation.

The approximation guarantee proceeds as follows. Let $v^{\ast }$ denote the optimal sumDp achievable by $k$ many $(1+\epsilon )$-approximate medians. First, we note that $v^{\ast }\gtrsim k^2{D}^{\ast }/4$. Next, we derive a lower bound on the sumDp value $v$ attained by our algorithm’s output (the final set of candidate medians). Let $U$ be the total remaining budget across all candidate medians in $S$ at the end of the algorithm, and let $\rho$ be the maximum density among the operations that were not performed. The core of the argument is to establish the two statements: $U\cdot \rho \lesssim k^2$, and $v^{\ast }-v\le U\cdot \rho$. Informally, $U\cdot \rho$ upper-bounds the additional sumDp one could gain by executing all leftover operations without violating any budget constraints. The main technical hurdle lies in proving these two bounds. This immediately yields an approximation factor of $(1-4/D^{\ast })$. The details appear in the full version.

For the problem of selecting $k$ approximate Hamming medians while maximizing the min dispersion, just like the case of exact medians, we can get a dynamic programming algorithm in polynomial time for $k=O(1)$. Thus, from now on, we focus on $k\ge \mathrm{\Omega }(1)$. Then we split into cases depending on the value of the optimal diameter $D^{\ast }$. When $D^{\ast }\le O(1)$, the number of candidate Hamming medians is polynomially bounded; in this case, applying the greedy min-dispersion heuristic [32] yields a $1/2$-approximation. For $D^{\ast }\ge \mathrm{\Omega }(\log k)$, we first compute two $(1+\epsilon )$-approximate Hamming medians $y,z$ of distance equal to the diameter (using Theorem 1). Then for each index $i$, we create an alphabet set ${\mathrm{\Gamma }}_i=\{y_i,z_i\}$. Next, we generate $k$ candidate approximate median strings via the following randomized procedure: For each index $i$, we select a character from ${\mathrm{\Gamma }}_i$ independently and uniformly at random, and repeat this process to form $k$ strings. We first argue that each resulting string is an $(1+2\epsilon )$-approximate median. Using concentration bounds, we establish a lower bound on the min dispersion minDp for these strings, and combining this with the fact that the optimal min dispersion can at most be the diameter, we obtain $\text{minDp}\gtrsim t^{\ast }/2$, where $t^{\ast }$ denotes the optimal minDp achievable by a set of $k$ many $(1+\epsilon )$-approximate medians. This yields a bi-criteria approximation. We can further improve this approximation factor for the “higher regime” of $t^{\ast }$. We formulate the problem using an integer linear program and consider its LP relaxation. Then, using a dependent rounding framework, we show that we can generate $k$ many $(1+\epsilon +\delta )$-approximate medians (for any $\delta >0$) with $\text{minDp}\ge (1/2-\delta )t^{\ast }$. We detailed the arguments in the full version.