A Scalable and Unified Framework to Weighted Rank Aggregation Amir Carmel∗
Debarati Das†
Tien-Long Nguyen‡
Abstract
arXiv:2605.09653v1 [cs.DS] 10 May 2026
The rank aggregation problem, seeks to combine multiple rank orderings of the same set of candidates into a single consensus ordering. Such problems arise in diverse domains, including web search, employment, college admissions, and voting. In this work we focus on the 1-median objective: given a set of m rankings over [n], the goal is to compute a ranking that minimizes the sum of its distances to all input rankings. We study rank aggregation under several classical distance metrics: Ulam distance, Spearman’s footrule, Hamming distance, and Kendall-tau, as well as their weighted variants. Our contributions begin with a novel unified framework that identifies a key structural property: it suffices to focus on a small subset of rankings (of size three or five), where the corresponding local one-median provides a good approximation to the global median. This principle extends across these distance measures, yielding a general algorithmic framework for weighted rank aggregation. Building on this, we present a new approximation algorithm for rank aggregation under the Ulam distance that scales in the Massively Parallel Computation (MPC) model. Our algorithm computes a (2 − α)-approximation, for a constant α > 0, to the 1-median in a constant number of rounds, using local memory sublinear in n (the size of a ranking) and total memory near linear in n. We further design new MPC approximation algorithms for Spearman’s footrule and for the element-weighted variants of Hamming and Kendall-tau distances. For each metric, we obtain a (2 − ζ)-approximation, for a constant ζ > 0 (which may differ across metrics), to the 1-median in a constant number of rounds, using local memory sublinear in n and total memory linear or near-linear in n. Moreover, for the Ulam distance, where computing the 1-median is NP-hard [Fischer et al., ESA, 2025], we simplify and strengthen the analysis of Chakraborty et al. [ITCS 2023], obtaining an improved 1.968-approximation that further extends to the weighted setting.
∗
Weizmann Institute of Science, Rehovot, Israel. [email protected]. Pennsylvania State University, University Park, PA, USA. [email protected]. ‡ Pennsylvania State University, University Park, PA, USA. [email protected]. †
1
Introduction
Aggregating inconsistent information from diverse sources is a fundamental challenge across disciplines such as social choice theory and information retrieval. The task of reconciling potentially conflicting preferences into a single consensus ranking is known as rank aggregation. This wellstudied problem traces back to the late 18th century, when Condorcet and Borda introduced early voting systems for elections with more than two candidates. In modern settings, rank aggregation continues to play a central role in applications ranging from sports and elections to search engines, databases, web evaluation systems, and statistics [16, 6, 30, 28, 12, 31, 29]. The complexity of the problem is amplified when disagreements or cycles arise in the input rankings, reflecting the conflicts among different sources. Addressing these inconsistencies to produce a meaningful consensus makes rank aggregation a critical and widely impactful data aggregation task. Given a set of n items, a ranking can be represented by a permutation π on [n]. To compare different rankings, several distance measures have been introduced, including Kendall-tau distance [26, 15, 25, 27, 2, 30] (also known as Kemeny distance in the context of rank aggregation), Hamming distance [13], Spearman’s footrule distance [36, 37, 15, 16, 30], and Ulam distance [10, 11, 17] (see Section 1.1 for formal definitions). Among the most studied aggregation frameworks are median rank aggregation (or simply rank aggregation) [25, 39, 40, 16] and maximum rank aggregation [5, 34, 8], which aim to find the median and the center ranking of a given set, respectively. In this paper, we consider the continuous version of these problems where the median/center can be any permutation from the input metric space. Rank aggregation is computationally tractable under Hamming distance and Spearman’s footrule, where exact solutions can be obtained using straightforward minimum-cost bipartite matching algorithms. In contrast, under Kendall-tau and Ulam distance, the problem is NPhard [3, 2, 17]. Nevertheless, a folklore 2-approximation follows directly from the triangle inequality, and a series of works have pushed beyond this trivial approximation. In particular, there exists a PTAS for Kendall-tau [27] while for Ulam distance [10, 11] achieved a 1.999approximation. Traditional rank aggregation metrics, as discussed above, treat all errors uniformly, overlooking the fact that in real-world settings, some mistakes are more costly than others. In information retrieval, for instance, misplacing a highly relevant document should incur a much larger penalty than misplacing an irrelevant one. This motivates the use of element weights, where each item is assigned a relevance score, and mistakes involving high-weight elements are penalized more heavily [30, 35]. In many applications, rank aggregation must be performed on massive datasets, where not only is the number of rankings large, but also the size of each ranking. For instance, scholarly search engines such as Corpus rank over 200M papers [33], e-commerce platforms order millions of products [38], and genomic studies combine extensive datasets to prioritize disease-associated genes [1]. Handling such large-scale data naturally motivates the design of efficient parallel algorithms. In particular, this large-scale setting presents two primary computational challenges: handling a large number of input rankings m, and processing rankings of large size n that may exceed the memory capacity of a single machine. We address the first challenge using sampling techniques, working with only a polylogarithmic-sized sample of the input rankings. The second challenge is more substantial and necessitates distributed parallel computation, naturally motivating the design of efficient parallel algorithms. In particular, when n is large, even storing a single ranking on one machine may be infeasible, requiring rankings to be distributed across multiple machines. A well-studied framework for this purpose is the Massively Parallel Computation (MPC) model [4, 7, 18, 24]. In this model, each machine has full access to its own local memory, but
1
communication between machines occurs only between rounds. Thus, the round complexity of an algorithm becomes the central performance measure, since network communication is typically the main bottleneck in practice. The ultimate objective is to design constant-round algorithms, which are highly desirable for large-scale systems. Despite its importance, rank aggregation has not been well studied in the massively parallel setting, and existing algorithms cannot be implemented directly in the MPC model. For instance, algorithms for Hamming or Spearman’s footrule rely on min-cost matching, but efficient implementations of matching in constant rounds with memory sublinear in the number of vertices are not known, necessitating new scalable approaches. In this work, we introduce a generalized framework that can be deployed in scalable settings and apply it to several classical rank aggregation measures.
1.1
Problem formulation and preliminaries
Let (X , dist) be an arbitrary metric space. Consider a finite set P = {p1 , p2 , . . . , pm } ⊆ X . For a given x ∈ X , we define the cost function as m
1 X cost(x, P ) = dist(x, pi ). |P | i=1
The 1-median problem seeks to find a point in X that minimizes this cost function. Let x∗ ∈ X be an optimal solution for P , that is, x∗ = arg minx∈X cost(x, P ), and denote OPT = cost(x∗ , P ) as the optimal cost. Note that x∗ may not be unique; when multiple optimal solutions exist, we fix an arbitrary choice. While our framework is conceptually applicable to general metric spaces, in this paper we focus on the case where X = Sn is the set of all permutations on [n] elements, and dist is some distance metric over Sn . This setting is also known as the rank aggregation problem. Specifically, we study four classical distance measures on permutations: Spearman’s footrule distance, Hamming distance, Kendall-tau distance, and Ulam distance, along with the elementweighted variants. Spearman’s footrule distance measures the ℓ1 distance between the position vectors of two permutations: n X distF (p, q) = p[i] − q[i] i=1
Hamming distance measures the number of positions where two permutations differ: distH (p, q) =
n X
1p[i]̸=q[i] .
i=1
The weighted version penalizes mismatches proportionally to the average weight of the mismatched elements: n X w(p[i]) + w(q[i]) w distH (p, q) = 1p[i]̸=q[i] . 2 i=1
Kendall-tau distance measures the number of elements pairs (e, e′ ) such that the relative order of e and e′ is reversed between permutations p and q. Formally, distτ (p, q) =
{e, e′ } : (p−1 [e] − p−1 [e′ ])(q −1 [e] − q −1 [e′ ]) < 0
2
where p−1 [e] is the position of the element e in the permutation p. The weighted version penalizes inversions proportionally to the average weight of the two elements: X
distw τ (p, q) =
e<e′ (p−1 [e]−p−1 [e′ ])(q −1 [e]−q −1 [e′ ])<0
w(e) + w(e′ ) . 2
Ulam distance measures the minimum number of move operations required to transform one permutation into another, where a move operation removes an element and reinserts it at a different position. We express this using the Indel distance (also known as LCS distance), which counts single-character insertions and deletions. The Indel distance is exactly twice the Ulam distance, since each move corresponds to one deletion followed by one insertion. 1 distU (p, q) = n − LCS(p, q) = ID (p, q) 2 In the weighted variant, each insertion or deletion of element i has cost w(i). Thus, the total weighted distance equals the sum of weights of all elements that must be moved to transform one permutation into the other. Framework. Our framework relies on analyzing the geometric structure of the metric space through the following key quantity. For an element x ∈ X and a pair i, j ∈ [m], we consider the triangle inequality slack ∆i,j (x) = dist(x, pi ) + dist(x, pj ) − dist(pi , pj ). This quantity is twice the Gromov product, a fundamental concept in hyperbolic geometry. By the triangle inequality, we have ∆i,j (x) ≥ 0 for all i, j ∈ [m] and x ∈ X . Finally, for any subset Q ⊆ P , we define the total slack as X ∆(x, Q) = ∆i,j (x). (1) i<j, pi ,pj ∈Q
While the total slack depends on the set Q, we omit Q as it is clear from context, and further denote ∆∗ = ∆(x∗ ) the total slack of the optimal median. A small total slack of x with respect to Q means that while the points in Q are mutually distant from one another, x serves as an effective median for the entire set. Note that, X |Q| ∆(x) = 2 cost(x, Q) − dist(pi , pj ). 2 i<j, pi ,pj ∈Q
It follows that an optimal median of Q minimizes the total slack, and in particular min ∆(y) ≤ ∆∗ . y∈X
(2)
The inequality holds because x∗ , which is optimal for P , need not be optimal for the subset Q. MPC Model. Throughout this paper, we assume the input consists of m permutations on [n]. In the MPC model [4, 7, 18, 24], both the number of machines and the local memory per machine are required to be significantly smaller thanthe input size. Accordingly, we fix a e n1−ϵ memory1 , and aim to minimize the parameter 0 < ϵ < 1, assume each machine has O total number of machines used by the algorithm. 1
e ) = O(f · polylogf ) Throughout, O(f
3
An MPC algorithm proceeds in a sequence of rounds. Within each round, every machine performs computations on the data stored in its memory. No communication is allowed during a round; instead, communication occurs only between rounds, with the restriction that the amount of data received by any machine does not exceed its memory capacity. Furthermore, any data output by a machine must be computed solely from the data already present locally. The input data is initially distributed across the machines.
1.2
Our contribution
In this paper we propose a new unified framework for providing approximate solutions to the 1median problem for various ranking measures. The key idea can be summarized by the following principle: If no input point serves as a good median, then there exists a constant-size subset Q ⊆ P such that a good approximation to the 1-median over Q lies within a small distance of the optimal solution for P . We refer to the approximation over Q as a local solution and the optimal median for P as the global median. The main advantage of this framework lies in its efficiency: since the subset Q is small, it is computationally efficient to obtain a local solution y that is optimal or near-optimal for Q, and the distance between x∗ and y can be bounded using the slack expressions ∆(x∗ ) and ∆(y). While Chakraborty, Das, and Krauthgamer [11] also proposed a construction for approximating the median from a small number of input permutations, their approach relies on combinatorial properties specific to the Ulam distance. In contrast, our local-vs-global property is significantly more general, yielding a broader and unified approach that applies to a variety of ranking problems. Furthermore, the framework of [11] has inherent bottlenecks that limit its applicability in distributed settings. In contrast, our first contribution is to show that our framework is sufficiently robust to be deployed in distributed settings. We design new algorithms in the Massively Parallel Computation (MPC) model that compute approximate medians over such subsets Q. This scalability is crucial for modern applications involving massive datasets, where both the number of rankings and the length n of each ranking are large, making it impractical for a single machine to process even one ranking [1, 33, 38]. Following this we propose the first approximation algorithm breaking the2-factor barrier for rank aggregation under Ulam distances in the e n1−ε memory per machine, total memory near-linear in n: the size of MPC model, using O ranking , and a constant number of rounds. Theorem 1.1. For any constants δ > 0, ε ∈ (0, 1/8),2,3 there exists a polynomial-time MPC algorithm that, given a set of m permutations P ⊆ Sn , computes, with high probability, a (2−α+ O (δ))-approximation to the 1-median under the Ulam distance, where α > 0 is a constant.4 The e n1+6ε , and requires O e n1−ε algorithm uses O (1) communication rounds, has total space O local memory per machine. Next, we show the applicability of our framework to weighted rank aggregation by establishing this property for the element-weighted variants of Kendall-tau, Hamming, and Ulam distances, and for Spearman’s footrule. More importantly, we show that the framework extends beyond mere generality and remains sufficiently robust even in the weighted setting. Building on this framework, we propose the first approximation algorithms breaking the 2-factor barrier for rank aggregation under Spearman’s footrule and the element-weighted variants of Hamming e n1−ε memory per machine, linear or and Kendall-tau distances in the MPC model, using O near-linear total memory, and a constant number of rounds. 2
The algorithm we present in this paper works with 0 < ε < 1/8. However, 1/8 < ε < 1 is not a barrier to our technique. For a sufficiently small constant ε > 0, the algorithm uses local memory sublinear in n and total memory near-linear in n. 3 Smaller δ yields better approximations but requires sampling more permutations from the input, increasing both space complexity and running time by constant factors. 4 Our analysis gives α = 0.000007. This constant has not been optimized and can be further improved.
4
Theorem 1.2. For any constant δ > 0, and ϵ ∈ (0, 1), there is a polynomial time MPC algorithm that, given a set of m permutations P ⊆ Sn , with high probability computes the following: • (1.75 + O (δ)) approximation of 1-median under Spearman’s footrule distance and elemente (nϵ ) processors each weighted Hamming distance using O (1) communication rounds, and O 1−ϵ with O n local memory. • (1.9+O (δ)) approximation of 1-median under element-weighted Kendall-tau distance using e n2ϵ processors each with O n1−ϵ local memory. O (1) communication rounds, and O Next, we simplify the analysis of [11], improve the approximation factor from 1.999 to 1.968, and extend the result to the weighted Ulam metric. In contrast to prior work, which is restricted to the unweighted setting, we present the first approximation algorithm for computing a median under the element-weighted Ulam distance. Theorem 1.3. There is a polynomial time algorithm that, given a set of m permutations P ⊆ Sn , provides a 1.968-approximate solution to the 1-median problem under the element-weighted Ulam metric with high probability. Note that in our problem the total input size is O(mn). A traditional MPC model only enforces that local memory is sublinear in the input size. In contrast, our results guarantee significantly stronger bounds by requiring local memory to be only sublinear in n. This is particularly important since, in most real-world applications, the number of rankings m can be much larger than the size of each ranking n. Finally, we note that our framework, particularly the local-global principle, is not specific to permutations and may extend to other metric spaces where a below-2 approximation for the 1-median problem remains open. For example, the edit distance metric for the well-known median string problem [20, 10], and the Fréchet distance or Dynamic Time Warping metrics for the average curve problem [9].
1.3
Technical overview
Framework Overview. Our general framework operates under the assumption that no point in P achieves cost better than (2 − α)OPT for some constant α ∈ (0, 1). Otherwise, we can achieve a (2 − α)-approximation by simply returning the minimum-cost point from the input set. With this assumption, the framework relies on two key properties: Property 1 (Universal). For every 2 ≤ r ≤ m, there exists a subset Q ⊆ P of size r such that r ∗ ∆ ≤α OPT. (3) 2 Property 2 (Metric-specific). There exists a constant r such that for every subset Q ⊆ P of size r and every y ∈ X , dist(x∗ , y) ≤ ∆(x∗ ) + ∆(y). (4) Property 1 holds universally for all metric spaces. We prove this through an averaging argument by considering the pairwise distances of points in P and expressing them using the distances from the optimal median x∗ . This intuitively suggests that for any two permutations in Q, their distance is approximately equal to the sum of their respective distances to the optimal median. However, Property 2 must be established individually for each metric. When it holds and y is an optimal median of Q, Equation (2) implies dist(x∗ , y) ≤ 2∆∗ . This means x∗ and y are close, so y serves as a good median for P , establishing the local-global property. For local solutions, where y is not optimal median of Q, we demonstrate how ∆(y) can be bounded in terms of ∆∗ for our specific metrics. A detailed analysis of our framework is given in Section 2. 5
New Scalable Approximation Algorithms for 1-Median under Ulam Distance. Building on the above framework, in Section 3 (algorithm description), and Section 4 (analysis) we present a new approximation algorithm for the 1-median under the Ulam distance, which we later show can be adapted to the MPC setting. For the Ulam metric, we assume that the set Q contains five permutations. A natural baseline approach for computing the 1-median of the permutations in Q is to apply a dynamic programming algorithm. However, this approach is not space-efficient, as it requires n5 space, which is prohibitive in the MPC setting. An alternative is to adapt the strategy from [11]. In this approach, an element is called bad if it is not aligned in an optimal alignment between a permutation in Q and the optimal median for at least two permutations in Q. Let the bad set denote the collection of all such elements. The algorithm constructs a tournament graph by taking the majority relative order for each pair of elements induced by the permutations in Q, then removes cycles and outputs a topological ordering. The main bottleneck of this approach is the cycle-removal step. In [11], the algorithm repeatedly identifies the shortest cycle and removes all its vertices. Since the graph is a tournament, the shortest cycle always has length three, and it can be shown that at least one vertex in each such triangle must be bad, which allows bounding the number of good elements removed. However, this approach does not extend to the MPC model. Because no single machine can store an entire permutation, a 3-cycle (a, b, c) may not be present on any one machine and therefore may go undetected. One possible workaround is to ensure that every triple of elements is collocated on at least one machine. But this leads to further complications: a single element may appear on many machines, and different machines may independently select distinct triangles involving the same vertex (e.g., (a, b, c) and (a, d, e)). This is problematic because the [11] analysis crucially relies on the selected cycles being vertex-disjoint in order to bound the number of good elements removed. It is nontrivial to reconcile these independently detected cycles while maintaining vertex disjointness in the MPC setting. This difficulty forms the main obstacle to implementing prior approaches. To overcome this, we propose a new framework and algorithm that provides a local solution for the permutations in Q. First, fix an optimal median of Q, denoted by y. We partition y into blocks of length κ = n1−ε , for some constant ε > 0. Our goal is to construct, for each such block of y, a substring of comparable length that provides a good approximation whenever the objective value of the block is not large. We classify an objective value as large if it is at least κ/ρ, where ρ > 0 is a small constant to be specified later. If the objective value is large, we instead use a block consisting only of dummy elements, which already yields a sufficiently good approximation. Furthermore, when approximating a block, we focus only on the good elements and ignore the bad elements. This is valid because the total number of bad elements is small and their cumulative contribution to the objective is large, allowing them to be handled arbitrarily. For this we devise a four-step process. Windows Decomposition: For each permutation π ∈ Q, fix an optimal alignment between π and y. Let q be a block of y. Define eℓ ∈ q to be the leftmost element of q that is matched in the optimal alignment between π and y, and define er ∈ q to be the rightmost element with this property. Suppose eℓ is matched to π[i] and er is matched to π[j]. We define π q to be the substring π[i, j]. The collection of substrings {π q : π ∈ Q} suffices to reconstruct q; we refer to these substrings as the constructive blocks. The main challenge is to identify these constructive blocks efficiently. We now describe a window decomposition for the permutations in Q, beginning with several observations specific to our problem. A key difficulty is that constructive blocks may have highly variable lengths. We first consider the case where at least one constructive block is very large, for example of size greater than k|q| for some sufficiently large constant k. In this situation, the objective value of q is already large, and therefore a trivial approximation using a block of 6
dummy elements suffices. Next, consider the case where at least two constructive blocks are very small. Then many elements of q do not appear in both of these blocks and hence remain unmatched in at least two permutations from Q. Such elements are therefore bad elements. This implies that the number of bad elements in q is large. Since the total number of bad elements across all blocks is small, this scenario cannot occur frequently. Consequently, in this case as well, a good approximation can be obtained by using a trivial block consisting only of dummy elements. From this point onward, we assume that no constructive block is too large and that at most one constructive block is very small. Even under this assumption, the constructive blocks may still have different sizes. To handle this, we introduce a windowing strategy that, for each permutation π ∈ Q, generates windows of variable sizes starting at various indices. We ensure that for every constructive block π q whose size is neither too large nor too small, there exists a window π[i′ , j ′ ] such that |i − i′ | + |j − j ′ | ≤ ρ · obj(q), where obj(q) denotes the objective value of the block q. A crucial aspect of this strategy is that we allow windows of size zero to handle very small constructive blocks, and we consider such zero-length windows at multiple starting indices. We provide the details of the window decomposition Block Reconstruction: Next, using these windows as constructive blocks, we attempt to estimate the blocks of y. Since we do not know in advance which windows correspond to a particular block, we try various choices of five windows. Specifically, we form constructive groups by selecting one window from each string in Q using a structured method rather than enumerating all combinations. Fix an arbitrary choice of five windows (constructive blocks), forming a constructive group. We first construct a graph whose vertices correspond to elements that appear in at least four constructive blocks. This restriction is justified because we only aim to approximate the good elements: any element that does not appear in at least four blocks is classified as a bad element. For each pair of vertices, corresponding to two elements c and d, we orient the edge between them as follows: we add an edge from c to d if c appears before d in at least three of the five blocks, and an edge from d to c if d appears before c in at least three blocks. If neither direction has a strict majority, we add no edge and delete both vertices c and d. This is valid because the absence of a majority implies that at least one of c or d is a bad element. Since the total number of bad elements is small, the number of good elements deleted in this process is also small. After this pruning step, the resulting graph is a tournament. This property is crucial for the next phase, where we remove cycles. We iteratively find the shortest cycle in the graph and delete all vertices in that cycle. Because the graph is a tournament, the shortest cycle has length at most three, and among the vertices of such a cycle, at least one must be a bad element. Moreover, since the cycles removed in different iterations are vertex-disjoint, the total number of good elements deleted remains bounded by the number of bad elements. Once the graph becomes acyclic, we compute a topological ordering of the remaining vertices, which yields a candidate block for the constructive group. For the subsequent dynamic programming step, we ensure that each candidate block has length at least κ. Thus, if the string obtained from the topological ordering has length less than κ, we pad it with dummy elements to reach length κ. The details of this step are provided in Section 3.3. Block Composition via Dynamic Programming: In Section 3.4, we combine these candidate blocks, each of length at least κ, using dynamic programming to obtain a good approximation of y. Since the dynamic program operates on blocks, the total state space is polynomial in n/κ = nε . Consequently, the DP can be implemented in the MPC setting within a single round by storing all blocks on one machine. An important subtlety is that, as discussed earlier, for some blocks of y the corresponding constructive blocks may be either very large or very small. In such cases, we approximate the 7
block of y using a block consisting entirely of dummy elements. However, we do not include these dummy-only blocks explicitly in the dynamic program, as doing so would significantly increase the space requirements. Instead, they are handled implicitly within the DP formulation. The output of the dynamic program is a string that provides a good approximation of y over the good elements. Moreover, each element appears at most once in this string. This property is guaranteed by the construction of the graph used in the previous step, where a vertex corresponding to an element is included only if the element appears in at least four constructive blocks. Post Processing: The DP output may omit some elements and may include dummy elements As argued earlier, the number of such elements is small and bounded by the number of bad elements. To convert the output into a permutation, we replace each dummy element with a missing element. One simple approach would be to delete all dummy elements and append the missing elements at the end, which would still yield a good approximation. However, our chosen strategy is crucial for enabling an efficient implementation in the MPC setting. The details are given in Section 3.5. New Scalable Approximation Algorithms for 1-Median with Element Weights. In the element-weighted setting although exact (or almost exact) 1-median algorithms may exist for computing the median of Q, they may not be directly adapted to the massively parallel setting. Such is the case for the rank aggregation problem under Hamming, Spearman’s footrule and Kendall-tau. To this end, we design algorithms that are scalable and are well-suited for implementation in the MPC model Again, the cornerstone of our approach is to devise a consensus strategy among the permutations in Q. We then show that for the relevant r, this consensus is close to the optimal median of the entire set P . We establish these distance bounds using the total slack term, which provides a unified framework across metric spaces. The details and analysis of the algorithms are presented in Section 5. Hamming Distance. Our algorithm constructs a consensus by selecting the majority element at each position where one exists among the three permutations in Q. The reasoning for selecting the majority as the basis of our consensus strategy is that if the optimal median does not follow the majority, then both input permutations supporting the majority will differ from the optimum, thereby increasing their slack. Since the total slack is assumed to be small (by Equation 3), this situation cannot occur frequently. Positions without majority agreement are filled arbitrarily with the remaining elements. The key insight is that such positions are exactly those contributing to the total slack: since they lack a majority, they affect both the local solution and the global optimum equally. Importantly, this property holds even in the element-weighted setting, making our consensus strategy robust to weights and yielding a 1.75-approximation. Spearman’s Footrule. We construct a consensus by taking the median element at each position across the three permutations, which yields a pseudo-permutation that may contain duplicates. This consensus is then converted into a valid permutation by sorting the elements and reassigning ranks according to their sorted order. While it is clear that taking the median value at each position minimizes the median cost, it is less obvious that this remains optimal once we enforce the consensus to be a valid permutation. Our key observation is that whenever the optimal median permutation selects a value different from the position-wise median, the slack increases for at least a pair of inputs. For example, suppose at position i the three input permutations π1 , π2 , π3 have values a ≥ b ≥ c. If the median instead uses some b′ ̸= b (say b′ > b) at index i, then the slack of π2 and π3 at this position increases by 2(b′ − b). Since the total slack is assumed to be small, such deviations cannot occur frequently. Thus, even under the constraint that the output must be a permutation, taking the position-wise median remains the best consensus strategy. This transformation ultimately yields 8
the closest valid permutation to our consensus under the Spearman’s footrule metric, resulting in an overall 1.75-approximation. Kendall-tau Distance. The Kendall-tau metric compares inversions between pairs of elements. The consensus is determined by majority vote over element pairs rather than positions. We construct a tournament graph where vertex a precedes vertex b if a appears before b in at least two of the three permutations. The resulting feedback arc set problem, solved via the KWIK-SORT algorithm, yields a permutation that respects the majority preference on most pairs. While the KWIK-SORT algorithm was applied to rank aggregation under the Kendalltau metric in [2] to obtain an approximate 1-median solution, the weighted setting requires a different approach. Using our framework, a weighted tournament is derived from the three input permutations, with edge weights assigned so that the triangle inequality holds, thereby enabling the use of the KWIK-SORT algorithm. Improved Approximation for Ulam Distance. Unlike the previous metrics, consensus under Ulam distance requires subsets Q of size 5. This follows from a more general property: for any two permutations x, y, we show the distance from x to y is at most ∆(x) + ∆(y). Combined with the universal Property 1, this enables us to improve the metric-specific analysis of [11] and naturally extend the result to the element-weighted variant. MPC Algorithm for Approximating 1-Median. We start by describing how permutations are represented in the MPC model and how pairwise distances are computed, primitives common to all metrics. Storing and Computing Distance in MPC: A key challenge in the MPC model is that e 1−ε ) local memory, which is insufficient to store an entire permutaeach machine has only O(n e ε ) machines. This tion; consequently, each permutation must be distributed across at least O(n sublinear memory constraint makes it nontrivial to compute a local solution and validate its cost even for a small subset Q of permutations, necessitating specialized MPC algorithms tailored to different distance metrics. Hamming and Spearman’s footrule distances can be computed in constant rounds using O (n) total space via block-wise aggregation. Kendall-tau distance requires n2ε machines to handle inversions between all block pairs, resulting in a total of O n1+ε space. Computing Ulam distance in MPC is more challenging, requiring the (1 + λ)-approximation e n1+ε space. algorithm of [19] with O A Sublinear Total Space Framework: We address the constraint on total memory through a sampling-based approach. Rather than enumerating all possible candidates, which may be as many as O (mr ), we show that it suffices to consider only O (log(n)) randomly selected input permutations and O (log(n)) local solutions derived from O (log(n)) random subsets of size r. To identify the best candidates, instead of computing their exact costs, we leverage results from [22, 23], which demonstrate that, with high probability, a (1 + δ)-approximate solution to the optimal candidate can be found by selecting the permutation with the minimum cost over a random sample of O log(n)/δ 2 input permutations. Next, we outline how to compute a local solution of the set Q under Ulam, Hamming, Spearman’s footrule, and Kendall-tau distances using constantly many communication rounds. Ulam distance. To employ our new algorithm for the Ulam distance in the MPC setting, we proceed in three phases. First, we distribute the task of constructing candidate blocks. For each group of five windows, we assign a specific machine to build the tournament graph, remove cycles, and output the resulting block. These results must then be aggregated to find the optimal combination of blocks. A direct approach would be to collect all candidate blocks onto a single machine to run the dynamic programming. However, this is not space-efficient, as the total size of these blocks may exceed the local memory of a single machine. To overcome this, we observe that the dynamic program does not need the actual strings; it only requires their objective values, lengths, and 9
the starting and ending indices of the corresponding windows. This summary information is small enough to fit in the memory of one machine, allowing us to compute the optimal sequence of blocks efficiently. The solution to the dynamic program implicitly defines a string consisting of nε blocks. Each block is either a candidate block stored on one of the distributed machines or a logical block consisting entirely of dummy elements. By backtracking through the solution, we can identify the specific machines holding the chosen candidate blocks and assign new machines to generate the required blocks of dummy elements. It remains to transform this distributed string into a valid permutation of length n. We first truncate the string by removing the leftmost dummy elements until the total length is exactly n. This is a simple counting task that can be performed using a broadcast tree of constant depth. Next, we must replace each remaining dummy element with a unique unused element. Our strategy is to pair the distinct unused elements with the remaining dummy positions according to their sorted order. That is, the k-th smallest unused element should be placed in the k-th available dummy position. To implement this matching, we need to compute the global rank of each unused element and each dummy position. Since the data is distributed, each machine first counts the unused elements it holds locally. Then, using a broadcast tree, each machine computes the total count of unused elements residing on all preceding machines. This allows every machine to determine the exact global rank of its elements. We apply the same procedure to rank the dummy positions. Finally, the elements and positions with matching ranks are routed to the same machine to complete the permutation. Hamming distance. In the algorithm for Hamming distance, (i) a majority element is assigned to each position if it exists among the permutations in Q. (ii) Positions without majority agreement are filled arbitrarily with remaining elements. The first step can be simulated in MPC similar to computing the Hamming distance: we bring the information from the i’th block of each permutation in Q to a single machine and decide the majority. The difficulty lies in the second step, as the list of unused elements and unassigned positions can be large and may not fit in a single machine. A simple approach is to assign unused elements in each i block to unassigned positions in the same block. However, this may not be feasible as the number of unused elements and unassigned positions in a block may differ. To resolve this, we consider the sorted list of unused elements and unassigned positions, and aim to pair them according to their order in the sorted lists. This requires computing the rank of each unused element relative to all unused elements, and the rank of each unassigned position relative to all unassigned positions. To implement this, we let each i’th machine keep the unused elements in the i’th block. The rank of each element can be computed if each machine knows the number of unused elements in all the previous blocks. This information can be made available to all machines by using a broadcast tree of depth max(1, 2ε−1 1−ε ). We proceed similarly for unassigned positions. Finally, the elements and positions with the same rank are sent to the same machine. Spearman’s Footrule. In the algorithm for Spearman’s footrule distance, we first compute a pseudo-permutation by assigning the median element at each position across the permutations in Q. The output permutation is obtained by sorting the elements in the pseudo-permutation and reassigning ranks according to their sorted order. The first step can be implemented in MPC similar to Hamming distance. The second step pose a similar challenge as in Hamming distance, since the elements are distributed across multiple machines. By sorting all elements in the pseudo-permutation, we reduce this problem to the pairing problem as in Hamming distance. Kendall-tau distance. For Kendall-tau distance, recall that we need to apply the KWIKSORT algorithm to solve the feedback arc set problem on the majority graph induced by Q. The KWIK-SORT algorithm starts with a random vertex as pivot, and partitions the remaining vertices into two sets according to the direction of the edges between them and the pivot. We 10
then recurse on the two sets, and concatenate the results. We follow a constant rounds MPC implementation of KWIK-SORT presented in [21]. The approach to simulate this in constant MPC rounds is to pick multiple pivots in each round. These pivots form a decision tree, which partitions the vertices into multiple sets. We then recurse on each set in parallel. However, if we directly follow the algorithm in [21], we will violate the local space constraint. In particular, [21] e (n), hence, they can choose O n1/2 pivots simultaneously in each allows the local space to be O round. Our local space may not be sufficient to accommodate this many vertices. We overcome this by choosing only O n1−ε vertices as pivots. Due to the fact that the size of partitioned sets can not be too large [21, Lemma 7], as long as the number of pivots is Ω(log(n)), the number 2 of rounds remains constant. Another challenge is that in [21], the total space is O n , as they need to store the edges explicitly. We resolve this by observing that we can access the direction of an edge by accessing the positions of two elements in the permutations in Q. This allows us to store the edges implicitly, keeping the total space at O (n). We provide the details of the MPC algorithms in Section 6. Organization. The remainder of the paper is organized as follows. Section 2 formalizes the general framework: we prove the universal Property 1 (Lemma 2.1) and combine it with the metric-specific Property 2 to obtain Algorithm 1 and its approximation guarantee (Theorem 2.2). Section 3 presents our new approximation algorithm ScalableMedianReconstruct for rank aggregation under the Ulam metric, describing each of its four steps: Window Decomposition, Block Reconstruction, Block Composition via Dynamic Programming, and PostProcessing. Section 4 is dedicated to the analysis of ScalableMedianReconstruct, culminating in the proof of Lemma 3.1. Section 5 establishes the metric-specific Property 2 for Hamming, Spearman’s footrule, Kendall-tau, and Ulam distances, yielding our offline approximation results for the weighted setting. Finally, Section 6 presents the MPC implementations of all four local-solution algorithms and yields our main MPC results, Theorems 1.1 and 1.2.
2
General Framework Analysis
In this section, we establish our framework and prove the components that are universal across all metric spaces. We begin by formalizing Property 1 in the following lemma. Lemma 2.1. Let P be a finite set of points in a metric space (X , dist). Assume that the number of points p ∈ P for which cost(p, P ) ≤ (2 − α)OPT is at most δm, for δ ∈ [0, 1 − α]. Let Q be a random subset of P of size r ≥ 2. Then, EQ [∆∗ ] ≤ 2r (α + 2δ)OPT. Proof. Let F = {p ∈ P | cost(p, P ) ≤ (2 − α)OPT} be the set of points from P with good approximation factor. From our assumption on the size of F , we have |F | ≤ δm, so we can lower bound the total cost X X X X cost(p, P ) = cost(p, P ) + cost(p, P ) ≥ cost(p, P ) ≥ (2 − α)(1 − δ)mOPT. p∈P
p∈F
p∈P \F
p∈P \F
On the other hand, we can express the same total cost by summing over all pairwise distances, X p∈P
cost(p, P ) =
m X 1 X p∈P
m
m
dist(p, pi ) =
i=1
m
1 XX dist(pi , pj ). m i=1 j=1, j̸=i
11
Using the definition of triangle inequality slack, we can write, m
m
m
m
1 XX 1 XX dist(pi , pj ) = dist(x∗ , pi ) + dist(x∗ , pj ) − ∆∗i,j m m i=1 j=1, j̸=i
=
2 m
i=1 j=1, j̸=i m m XX
m
dist(x∗ , pi ) −
i=1 j=1, j̸=i
m
1 XX ∗ ∆i,j m i=1 j=1, j̸=i
m
= 2(m − 1)OPT −
m
1 XX ∗ ∆i,j m i=1 j=1, j̸=i
Combining both bounds, m
(2 − α)(1 − δ)mOPT ≤ 2(m − 1)OPT −
m
1 XX ∗ ∆i,j . m i=1 j=1, j̸=i
Rearranging, m X m X
∆∗i,j ≤ (mα(1 − δ) + 2mδ − 2)mOPT ≤ (mα + 2mδ − 2)mOPT.
i=1 j=1, j̸=i
Since each pair {i, j} with i ̸= j appears twice in the double sum, and ∆∗i,i = 0, X 1≤i<j≤m
1 ∆∗i,j ≤ (mα + 2mδ − 2)mOPT. 2
For a subset Q of size r drawn uniformly at random from P , using linearity of expectation, X EQ [∆∗ ] = EQ ∆∗i,j = i<j pi ,pj ∈Q
X
∆∗i,j · Pr[pi ∈ Q, pj ∈ Q].
1≤i<j≤m
The probability that both pi and pj are selected in a random subset of size r is m−2 Pr[pi ∈ Q, pj ∈ Q] =
r−2 m r
.
Therefore, m−2 r−2 m r
∗
m−2 r−2 m r
1 · (mα + 2mδ − 2)mOPT 2 1≤i<j≤m r(r − 1) r = · (mα + 2mδ − 2)OPT ≤ (α + 2δ)OPT 2(m − 1) 2
EQ [∆ ] =
X
∆∗i,j ≤
where the last inequality holds for δ ≤ 1 − α. We formalize Property 2 as we apply it in our analysis. Property 2 (Metric-specific). For our framework to apply to a metric space (X , dist), we require the existence of constants C > 0 and r ≥ 2, and an algorithm that, given any subset Q ⊆ P of size r, produces a solution y such that dist(x∗ , y) ≤ C · ∆∗ . 12
The challenge is to design such an algorithm and establish this property for each specific metric space. We now combine both properties to design a general framework for the 1-median problem in the sublinear regime. Our framework operates by establishing that if only few points in P achieve a (2 − α)-approximation for some small constant α, then there exist many constant-size subsets Q ⊆ P with small total slack. Following Property 2 the algorithm applied on such Q produce a point that is close to the optimal global median. Hence, we construct a set of candidates C such that with high probability one of the candidates achieves a (2 − α)-approximation. We employ a sublinear approach that was developed by Indyk [22, 23] for the discrete 1-median problem, where the medians are restricted to a specific set of points. In [23] it was shown that sampling O δ −2 log n points is sufficient to identify a candidate that achieves a (1 + δ)-approximation to the best median in the candidate set C with high probability. See Algorithm 1 for the complete pseudocode. Algorithm 1: A space efficient general framework for 1-median approximation. Input : Set P ⊆ X , constant r, δ > 0 Output: Approximate 1-median solution 1 C ← a set of O (log n/δ) points sampled uniformly at random from P ; 2 for i ∈ {1, 2, . . . , O (log n/δ)} do 3 Q ← a set of r permutations sampled uniformly at random from P ; 4 y ← localAlg(Q); // compute a local solution over Q 5 C ← C ∪ {y} ; 6 Sample a set S of O log n/δ 2 permutations uniformly at random from P ; 7 return x := arg minx∈C cost(x, S);
Theorem 2.2. Let t(n) denote the time required to compute the distance between two permutations of length n. Assume Property 2 holds with constants C and r, and there is an algorithm that, given any subset Q ⊆ P of size r, in time tℓ (n) produces a solution y such that dist(x∗ , y) ≤ C · ∆∗ . Then Algorithm 1 returns with high probability a (2 − C r1 +1 + O (δ))(2) e (tℓ (n) + t(n)) time. approximation to the 1-median problem on P using O Proof. Approximation ratio analysis. Let α = (C 2r + 1)−1 . If the number of points p ∈ P for which cost(p, P ) ≤ (2 − α)OPT is at least δm, then w.h.p such a point is added to the set of candidates C. Otherwise, by Lemma 2.1, expected total slack of Q for every Q sampled is at most 2r (α + 2δ)OPT. Using Markov inequality, in Line 2, with high probability, we sample a set Q with at most 2r (α + 3δ)OPT. The output y of localAlg(Q) is added to C, furthermore, r ∗ ∗ following Property 2, dist(x , y) ≤ C∆ ≤ C 2 (α + 3δ)OPT. Then, by the triangle inequality, 1 X r ∗ ∗ cost(y, P ) ≤ (dist(y, x ) + dist(x , p)) ≤C (α + 3δ)OPT + OPT m 2 p∈P r ≤ (C (α + 3δ) + 1)OPT. 2 Using Indyk’s sampling method and our selection of α, we obtain Algorithm 1 return a (2 − α + O (δ))-approximation. Running time analysis. Line 2 repeats O (log(n)/δ) times, each executing localAlg in tℓ (n) time. Line 6 computes the cost of O (log(n)/δ) candidates to set S of size O log(n)/δ 2 e (tℓ (n) + t(n)). in O log(n)2 t(n)/δ 3 time. For a constant δ, the total running time is then O
13
3
New Approximation Algorithm for Rank Aggregation under Ulam Metric
In this section, we present our new approximation rank aggregation algorithm under Ulam metric. Using the framework we developed in Algorithm 1, it suffices to design a scalable algorithm on input Q consisting of r permutations, producing a permutation yoffline that is close to x∗ . Our contribution is a new offline polynomial-time algorithm, ScalableMedianReconstruct, which we implement in the MPC model using O (1) rounds (Section 6.1). This algorithm satisfies a variant of Property 2, as stated in Lemma 3.1. Lemma 3.1. Let Q = {π1 , π2 , . . . , π5 } be a set of five permutations from P . The output yoffline of ScalableMedianReconstruct with input Q satisfies ID (yoffline , x∗ ) ≤ 0.0009
5 X
ID (x∗ , πi ) + 266∆(x∗ ).
(5)
i=1
Additionally to Lemma 3.1, we require the following structural lemma which, which extends Lemma 2.1 with additional properties that we exploit in the Ulam case. α . Let P be a finite set of m points in a metric space Lemma 3.2. Let α ≤ 1 and δ ≤ 100 (X , dist), and assume that |{p ∈ P : cost(p, P ) ≤ (2 − α)OPT}| ≤ δm. Let Q be a uniformly random subset of P of size 5. Then with probability at least 0.008, both of the following hold:
(P1) dist(q, x∗ ) ≤ (1 + α)OPT for all q ∈ Q, and (P2) ∆(x∗ ) ≤ 510α · OPT. Proof. Let F0 = {p ∈ P | cost(p, P ) < (2 − α)OPT}, F1 = {p ∈ P | (1 − α)OPT ≤ dist(x∗ , p) ≤ (1 + α)OPT} . Recall |F0 | = δm and further denote |F1 | = γm for some γ ∈ [0, 1]. Then, OPT =
1 X dist(x∗ , p) m p∈P
≥
1 X 1 dist(x∗ , p) + m m p∈F1
X
dist(x∗ , p)
p∈P \(F0 ∪F1 )
≥ γ(1 − α)OPT + (1 − γ − δ)(1 + α)OPT. Solving for γ, we obtain
1 (1 + α)δ 1 1 − ≥ − , 2 2α 2 100 where the last inequality follows from our assumptions on α and δ. Consider a random subset Q of five permutations chosen uniformly from P . Let B denote the bad event that Q does not satisfy both ∆(x∗ ) ≤ 500(α + 2δ)OPT and Q ⊆ F1 . For the first condition, by Lemma 2.1 and Markov’s inequality, γ≥
1 . P[∆(x∗ ) > 500(α + 2δ)OPT] ≤ 50 α 1 Since δ ≤ 100 , we have 500(α + 2δ) ≤ 510α, and therefore P[∆(x∗ ) > 510α · OPT] ≤ 50 . For the second condition, the probability that not all five sampled points are from F1 is 1 5 1 1 − γ 5 ≤ 1 − 21 − 100 < 0.972. By the union bound, P[B] ≤ 50 + 0.972 = 0.992.
14
Theorem 3.3. For any constant δ > 0, there is a polynomial time algorithm that, given a set of m permutations P ⊆ Sn , with high probability computes a (2 − α + O (δ)) approximation of 1-median under Ulam distance, where α > 0 is a constant. Proof of Theorem 3.3. We utilize the framework of Algorithm 1 with r = 5 and in place of localAlg in Line 4, we use our algorithm ScalableMedianReconstruct. Our proof relies on Lemma 3.2, which describes a structural property of the input set under Ulam distance. Fix α = 0.000007. If the number of permutations in p ∈ P for which cost(p, P ) ≤ (2−α)OPT is at least δm, then w.h.p, such a permutation is included in C in Line 1 of Algorithm 1. Otherwise, Lemma 3.2 implies that a random set Q of 5 permutations satisfies properties (P1) and (P2) with probability at least 0.008. As we sample O (log n) sets in Line 2, w.h.p., such a set Q is included in the samples. In this case, the candidate set C contains a permutation y = ScalableMedianReconstruct(π1 , . . . , π5 ). From Lemma 3.1 and our choice of α, we have: ID (y, x∗ ) ≤ 0.0009(1 + α)OPT + 266 ∗ 510αOPT ≤ 0.96OPT. Consequently, by the triangle inequality: 1 cost(y, P ) ≤ m
m X
! ∗
∗
(ID (y, x ) + ID (x , pi ))
≤ ID (y, x∗ ) + OPT ≤ 1.96OPT.
i=1
In all cases, the candidate set C contains a permutation achieving a (2 − α)-approximation to the optimal 1-median. Choosing a candidate from C using Indyk’s sampling method [23] (lines 6–7 of Algorithm 1) returns a permutation with cost at most (2 − α + O (δ))OPT. As the algorithm ScalableMedianReconstruct runs in time polynomial in n (complete running time analysis provided in Section 3.5), it is clear that the overall algorithm runs in polynomial time. The remainder of this section describes the algorithm ScalableMedianReconstruct.
3.1
Overview of ScalableMedianReconstruct Algorithm
Our objective is to compute a good estimation of the median of Q, defined as y ∗ = arg min z∈Sn
5 X
ID (πi , z) .
i=1
To outline the algorithm, we first fix an optimal alignment between y ∗ and each input permutation πi for i = 1, . . . , 5. Consider a partition of y ∗ into nε disjoint contiguous blocks y ∗ [ℓj , rj ) of size κ = n1−ε . The fixed alignments induce a corresponding decomposition of each πi into substrings πi [αi,j , βi,j ), such that the block y ∗ [ℓj , rj ) aligns with πi [αi,j , βi,j ). We refer to each πi [αi , βi,j ) as a constructive block, and to {πi [αi,j , βi,j )}5i=1 as a constructive group. Each block y ∗ [ℓj , rj ) can be approximately reconstructed using the corresponding constructive group {πi [αi,j , βi,j )}5i=1 . We refer to these approximations as candidate blocks. The challenge lies in efficiently identifying these constructive blocks and combining the candidate blocks to obtain an overall approximation of y ∗ . The ScalableMedianReconstruct algorithm accomplishes this through the following four steps:
15
• Windows Decomposition: Each string πi ∈ Q is decomposed into windows, which serve as constructive blocks for building the blocks of y ∗ . We then form constructive groups by selecting one window from each string using a structured method, rather than enumerating all combinations. The details are provided in Section 3.2. • Block Reconstruction: For each constructive group, a candidate block is computed using the Block Reconstruction algorithm (Algorithm 2). These candidate blocks serve as primitives for the next step. The details are provided in Section 3.3. • Block Composition via Dynamic Programming: The candidate blocks from the previous step are combined to form an intermediate string s via a dynamic programming approach. The intermediate string s consists of nε blocks, each being either a string created in the Block Reconstruction step or a string of dummy elements of length κ. The details are provided in Section 3.4. • PostProcessing: The intermediate string s has length at least n and contains no repeated elements, but it may not be a permutation due to missing elements and the presence of dummy elements. To transform s into a permutation yoffline , we replace the dummy elements with the unused elements. The details are provided in Section 3.5. Throughout our algorithm, we use a small constant ρ > 0, the value of which will be specified later. We denote the dummy element by ∗.
3.2
Windows Decomposition
In this phase, we decompose the interval [1, n + 1) into a set of windows W. Each window is defined as a pair of start and end positions ⟨s, e⟩ such that 1 ≤ s ≤ e ≤ n + 1. We aggregate these windows into a set W ⊆ W 5 consisting of groups of five windows. Based on this set, we refer to a collection of five substrings {πi [si , ei )}5i=1 as a constructive group if {⟨si , ei ⟩}5i=1 belongs to W . S ε S ε We decompose [1, n + 1) into W = nj=1 Wj ∪ nj=1 Sj , where Wj and Sj are constructed as follows. For each ϕ such that nϕ belongs to the set {1, 1 + ρ, (1 + ρ)2 , . . . , (1 + ρ)⌈log1+ρ (2n)⌉ }, we select start positions s from the range [ℓj − nϕ , ℓj + nϕ ] that are divisible by g = ρnϕ−ε . The set Wj consists of windows starting at such positions s. For each s, the end positions are defined as: s + κ e = s + κ + (1 + ρ)a , 0 ≤ a ≤ log1+ρ min(κ/ρ, nϕ ) (6) a s + κ − (1 + ρ) , 0 ≤ a ≤ log1+ρ (κ − ρκ) The set Sj is a collection of degenerate windows of the form [s, s), where s is selected from the same set of start positions as above. We now describe how to group these windows to form W , thereby inducing the constructive groups. A Simple Grouping approach is to construct W = W 5 . Observe that Strategy. A simple 2 ε ε |Wj | = O n log n and |Sj | = O (n ). Consequently, the total size of the window set is |W| = O n2ε log2 n , leading to |W | = O n10ε log10 n . A Selective Grouping Strategy. To reduce the size of the set, we employ a more selective method. We define W as the union of sets W1 , W2 , . . . , Wnε , where each Wj is constructed as: Wj = Wj5 ∪
5 [
Wjk−1 × S × Wj5−k .
k=1
16
(7)
S Here, S = j Sj denotes the set of all degenerate windows. Since |S| = O n2ε , the size of each Wj is bounded by O n6ε log8 n . Therefore, the total size is reduced to |W | = O n7ε log8 n .
3.3
Block Reconstruction
For every constructive group {πi [si , ei )}5i=1 , we apply Block Reconstruction algorithm (Algorithm 2) with input {πi [si , ei )}5i=1 to construct a candidate block. This candidate block, along with the corresponding input intervals, is collected into a set Cj . Formally, for each j ∈ {1, . . . , nε },
Cj :=
5 5 5 Block Reconstruction πi [si , ei ) i=1 , ⟨si , ei ⟩ i=1 | ⟨si , ei ⟩ i=1 ∈ Wj .
The Block Reconstruction algorithm proceeds as follows. First, we construct a directed graph G = (V, E) where the vertex set V consists of all elements appearing in at least four of the five input substrings. For any pair of distinct vertices a, b ∈ V , we add a directed edge (a, b) to E if and only if a precedes b in a strictly greater number of substrings than b precedes a. Next, we prune G to obtain an acyclic tournament. We first iteratively remove any pair of vertices (a, b) that is not connected by an edge. Once every remaining pair is connected, the graph becomes a tournament. Since a tournament contains cycles if and only if it contains triangles, we iteratively identify triangles and remove their vertices until the graph is acyclic. Finally, we extract a string tp from the topological ordering of the remaining vertices. If the length of tp is less than κ, we append ∗ elements to extend it to length κ. The complete procedure is detailed in Algorithm 2. Algorithm 2: Block Reconstruction algorithm Input : A constructive group {πi }5i=1 . Output: A candidate block tp. 1 procedure BlockReconstruction(π1 , π2 , π3 , π4 , π5 ) 2 G ← (V, E) where 3 V = {a ∈ Σ | a appears in at least 4 strings}, 4 E = {(a, b) | count(a before b) > count(b before a)} 5 while there exists a pair of vertices {a, b} ⊆ V with no edge between them do 6 V ← V \ {a, b} 7 8
while there exists a triangle C in G do V ← V \ V (C)
12
tp ← topological sort of V if |tp| < κ then return tp∗κ−|tp| // pad with ∗ to get a string of length κ return tp
3.4
Block Composition via Dynamic Programming
9 10 11
We construct an intermediate string s by combining substrings constructed from the step Block Reconstruction. The string s consists of nε blocks, where each j-th block is either a string from a tuple a ∈ Cj , or a block consisting of κ dummy elements. We determine the specific composition of s by solving a minimization problem over the search space induced by the sets C1 , C2 , . . . , Cnε . To formalize this optimization process, we first specify the domain of valid solutions. 17
Figure 1: A valid sequence of tuples a1 ∈ C2 , a2 ∈ C6 , and a3 ∈ C8 induces a string s = σ1 σ2 . . . σ10 . This structure defines a decomposition of each input permutation πi and establishes the alignment between s and πi . Search space. We define the search space as the set of all strings induced by a valid sequence of tuples. Formally, for all 1 ≤ k ≤ nε and indices 1 ≤ j1 < j2 < · · · < jk ≤ nε , consider a sequence of tuples (a1 , a2 , . . . , ak ), where at ∈ Cjt . We call this sequence valid if for all 1 ≤ t < k, denoting at = (st , {⟨si,t , ei,t ⟩}5i=1 ) and at+1 = (st+1 , {⟨si,t+1 , ei,t+1 ⟩}5i=1 ), we have ei,t ≤ si,t+1 for all i = 1, . . . , 5. Any such valid sequence uniquely defines a string of nε blocks, denoted as sa1 ,...,ak = σ1 σ2 . . . σnε . The block σjt is the string component of the tuple at = (st , {⟨si,t , ei,t ⟩}5i=1 ), i.e., σjt = st . Any block σh where h ∈ / {j1 , . . . , jk } is filled with κ ∗ elements. This amounts to inserting (j1 − 1)κ elements before block σj1 , and (jt+1 − jt − 1)κ elements between blocks σjt and σjt+1 . Furthermore, this valid sequence defines a specific decomposition for each permutation πi . The indices of πi are partitioned into: [1, si,1 ), [si,1 , ei,1 ), [ei,1 , si,2 ), [si,2 , ei,2 ), . . . , [ei,k , n + 1). This structure imposes an alignment between the constructed string s and each πi : the explicit blocks σjt align with the intervals πi [si,t , ei,t ), while the segments of ∗ elements align with the prefix πi [1, si,1 ), the substrings πi [ei,t , si,t+1 ), and the suffix πi [ei,k , n + 1). We illustrate this alignment in Figure 1. Objective Function. Let BlockED(s) be the sum of distances between the blocks of s and the corresponding intervals of each πi defined by this decomposition. Since this represents the cost P of one specific alignment, BlockED(s) serves as an upper bound on the distance 5i=1 ID (s, πi ). Formally, k X 5 X
BlockED(s) =
+
(8)
ID (σjt , πi [si,t , ei,t ))
t=1 i=1 5 X
(9)
((j1 − 1)κ + si,1 − 1)
i=1
+
+
k−1 X
5(jt+1 − jt − 1)κ +
t=1 5 X
5 X
! (si,t+1 − ei,t )
(10)
i=1
(nε − jk )κ + n + 1 − ei,k .
i=1
The components of this equation correspond to the alignment segments as follows: 18
(11)
• The term (8) is the sum of local edit distances between each selected block σjt and the input interval πi [si,t , ei,t ). • The term (9) is the distance between the prefix σ1 . . . σj1 −1 of s (consisting of ∗ elements) and the prefix πi [1, si,1 ). • The term (10) is the distance between the gap substrings σjt +1 . . . σjt+1 −1 of s and the intervals πi [ei,t , si,t+1 ). • The term (11) is the distance between the suffix σjk +1 . . . σnε of s and the suffix πi [ei,k , n + 1). Finally, the string we construct is the solution to the following optimization problem over the defined search space: min BlockED(s), s
(12)
where the minimization is performed over all strings s induced by valid sequences of tuples. Dynamic Programming Solution. The minimization problem (12) can be solved using dynamic programming as follows. For convenience, for a tuple a = (s, {⟨si , ei ⟩}5i=1 ), we denote da =
5 X
ID (s, πi [si , ei )) .
i=1
Let D[a] be the minimum of BlockED(s), taking over all s induced from sequence of tuples in which a is the last tuple. The update rule for D[a] is given by D[a] = min
X 5
(si − 1) + 5(j − 1)κ + da ,
i=1
min
5 n o X D[b] + (si − e′i ) + 5(j − h − 1)κ + da
b∈Ch ,h<j b=(s′ ,{⟨s′i ,e′i ⟩}5i=1 ) e′i ≤si ,∀i=1,...,5
+
5 X
i=1
(n + 1 − eai ) + 5(nε − j)κ.
(13)
i=1
Finally, it is clear that the solution to (12) is given by min BlockED(s) = min ε D[a]. s
1≤j≤n , a∈Cj
In order to trace back the solution, we employ an array P [a] to keep track of the previous solution, that is, P [a] = b if D[a] is computed from D[b]. Let s be the string recovered by backtracking through these pointers. It is evident from the construction of valid sequences of tuples that s has length at least n and contains no repetitions. We provide a formal description for this phase in Algorithm 3.
19
Algorithm 3: Block Composition via Dynamic Programming Input: C1 , C2 , . . . , Cnε . 1 for j = 1 → nε do 2 for a ∈ Cj , a = (s, {⟨si , ei ⟩}5i=1 ) do P 3 da ← 5i=1 ID (s, πi [si , ei )) P 4 D[a] ← 5i=1 (si − 1) + 5(j − 1)κ + da 5 P [a] ← ∅ 6 for h = 1 → j − 1 do 7 for b ∈ Ch , b = (s′ , {⟨s′i , e′i ⟩}5i=1 do 8 if e′i ≤ si , for all i = 1, 2, . . . 5, and P D[a] > D[b] + 5i=1 (si − e′i ) + 5(j − h − 1)κ + da then P 9 D[a] ← D[b] + 5i=1 (si − e′i ) + 5(j − h − 1)κ + da 10 P [a] ← b 11 answer.D ← ∞ 12 for j = 1 → nε do 13 14 15 16
for a ∈ Cj do P if answer.D < D[a] + 5i=1 (n + 1 − eai ) + 5(nε − j)κ then P answer.D ← D[a] + 5i=1 (n + 1 − eai ) + 5(nε − j)κ answer.P ← a
17 return answer
3.5
PostProcessing
This step transforms the intermediate string s, obtained from Block Composition via Dynamic Programming step, into the final permutation yoffline . Interestingly, a naive strategy, simply truncating s to length n and replacing remaining ∗ elements with unused characters, suffices to preserve the desired approximation ratio. However, to ensure scalability in the MPC model, we follow a different strategy. First, we scan s from left to right, removing ∗ elements until the length reduces to n. Let s′ be the resulting string. Next, we replace each remaining ∗ element in s′ with distinct unused elements from Σ in increasing order. This yields the final output permutation yoffline . Runtime Analysis. We finish this section by arguing that ScalableMedianReconstruct algorithm runs in time polynomial in n. In step Windows Decomposition, constructing the set W of size O n7ε log8 n requires O n7ε log8 n time. The subsequent steps, Block Reconstruction and Block Composition via Dynamic Programming, run in time polynomial in the size of W ; since |W | is polynomial in n, these steps are also polynomial in n. Finally, step PostProcessing requires only O (n) time. Consequently, the overall runtime of the algorithm is polynomial in n.
4
Analysis for ScalableMedianReconstruct algorithm
In this section we prove Lemma 3.1. Lemma 3.1. Let Q = {π1 , π2 , . . . , π5 } be a set of five permutations from P . The output yoffline of ScalableMedianReconstruct with input Q satisfies ∗
ID (yoffline , x ) ≤ 0.0009
5 X i=1
20
ID (x∗ , πi ) + 266∆(x∗ ).
(5)
P Let y ∗ = arg miny∈Sn 5i=1 ID (y, πi ) be an optimal median of Q. The corner stone in our proof is to bound cost(yoffline , Q) in terms of cost(y ∗ , Q) and the total slack. Lemma 4.1. Let Q = {π1 , π2 , . . . , π5 } be a set of any five permutations from P . The output yoffline of ScalableMedianReconstruct with input Q satisfies 5 X
ID (yoffline , πi ) ≤ 1.000225
i=1
5 X
ID (y ∗ , πi ) + 66∆(x∗ ).
i=1
In Section 4.1, we introduce the notations and terminologies used in the analysis. We provide an overview of the proof of Lemma 4.1 in Section 4.2. The formal proof is detailed in Section 4.3, Section 4.4, Section 4.5, and Section 4.6. Finally, Section 4.7 completes the analysis by proving Lemma 3.1, using Lemma 4.1.
4.1
Notations and Terminologies Used in the Analysis
For any permutation x ∈ Sn , fix an optimal alignment between x and each πi in Q. For each i = 1, 2, . . . , 5, let Iπxi be the set of elements that are unaligned when comparing x with πi . Then Iπxi = ID (x, πi ). We define a bad set Bx as the set of elements that are unaligned when comparing x with at least two permutations from Q, [ Bx = (Iπxi ∩ Iπxj ). 1≤i<j≤5
Fix an optimal alignment between y ∗ and each πi in Q. Fix a partitioning of y ∗ into nε disjoint contiguous blocks of size κ = n1−ε , denoted by y ∗ [ℓj , rj ). Here rj − ℓj = n1−ε , and ℓj+1 = rj . This alignment decomposes each πi into nε substrings, denoted by πi [αi,j , βi,j ), such that the block y ∗ [ℓj , rj ) is aligned with πi [αi,j , βi,j ). Recall that ρ > 0 is a small constant we used in the algorithm ScalableMedianReconstruct. For each i = 1, 2, . . . , 5, let nϕi be a (1 + ρ)-approximation of ID (y ∗ , πi ), that is, ID (y ∗ , πi ) ≤ ϕ n i ≤ (1 + ρ)ID (y ∗ , πi ). Define gi = ρnϕi −ε , for simplicity, we assume that gi is an integer. We classify the intervals [αi,j , βi,j ) based on their length relative to the block size κ. An interval is called large if βi,j − αi,j > κ/ρ, small if βi,j − αi,j < gi + ρκ and medium otherwise. ′ , β ′ ) is called an approximation of [α , β ) if An interval [αi,j i,j i,j i,j ′ αi,j ≤ αi,j ≤ αi,j + ρnϕi −ε ′ βi,j − ρnϕi −ε − ρID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )) ≤ βi,j ≤ βi,j .
4.2
(14)
Overview of the analysis.
We analyze each step of ScalableMedianReconstruct algorithm. Analysis of Windows Decomposition We show that in this step, for any block y ∗ [ℓj , rj ), there is a constructive group {πi [si , ei )}5i=1 such that, for each i = 1, 2, . . . , 5, if the interval [αi,j , βi,j ) is medium, then the interval [si , ei ) satisfies the approximation condition in Equation (14). The details are provided in Section 4.3.
21
Analysis of Block Reconstruction Consider a target block y ∗ [ℓj , rj ) for which all five aligned intervals [αi,j , βi,j ) are medium. Recall that the previous step established the existence of a constructive group {πi [si , ei )}5i=1 in which each [si , ei ) approximates [αi,j , βi,j ). In this step, we demonstrate that the output y generated by Block Reconstruction on input {πi [si , ei )}5i=1 shares a long common subsequence with the target segment y ∗ [ℓj , rj ). A similar guarantee holds when [ℓj , rj ) is aligned with exactly four medium aligned intervals. In this scenario, there are also constructive groups {πi [si , ei )}5i=1 where four of them has [si , ei ) approximates the corresponding medium aligned intervals, and the remaining one is an empty string of the form πi [si , ei ) with si = ei . We show that the outputs of Block Reconstruction on such inputs also share a long common subsequence with y ∗ [ℓj , rj ). We refer to this specific invocation as running Block Reconstruction on four medium intervals. The detailed analysis is presented in Section 4.4. Analysis of Block Composition via Dynamic Programming We identify a string se = σ1 σ2 . . . σnε in the search space of Block Composition via Dynamic Programming, such that BlockED(e s) can be bounded from above. In this string se, a block σj is a κ-length string of ∗ elements if either there is at least one permutation πi with large aligned interval [αi,j , βi,j ), or there are at least two permutations πi , πi′ with small aligned intervals [αi,j , βi,j ), [αi′ ,j , βi′ ,j ). In the remaining case, where for the j-th block there are at least 4 permutations πi with medium aligned intervals [αi,j , βi,j ), recall that we have established the existence of a constructive group {πi [si , ei )}5i=1 in which [si , ei ) approximate these [αi,j , βi,j ). Specifically, [si , ei ) approximates the medium interval [αi,j , βi,j ), while for any i with a small aligned interval, we have si = ei . We define σj as the output of Block Reconstruction on input {πi [si , ei )}5i=1 . By construction, the resulting string se lies within the search space of Block Composition via Dynamic Programming. We argue that se is close to the median y ∗ of Q. This is a consequence obtained from an upper bound on the sum of distance between each block σj and its corresponding block y ∗ [ℓj , rj ). The argument proceeds differently for different types of blocks: • From the analysis for Block Reconstruction algorithm, each block σj obtained from Block Reconstruction algorithm shares a long common subsequence with the corresponding block y ∗ [ℓj , rj ). • For the blocks y ∗ [ℓj , rj ) such that there is at least one permutations with the large aligned interval [αi,j , βi,jP ), then the distance between y ∗ [ℓj , rj ) and any string of length κ is dominated by 2κ ≤ 5i=1 ID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )). • For the remaining blocks, there are at least two permutations with small aligned intervals. We show that this case does not happen too often. The closeness between se and y ∗ allows us to upper bound the sum of the distances between se and each permutation πi . More precisely, we derive an upper bound for BlockED(e s). The output s of Algorithm 3 is a string achieving the minimum BlockED in the search space, and therefore, BlockED(s) ≤ BlockED(e s). We present the detailed analysis in Section 4.5. Analysis of PostProcessing The output in PostProcessing is obtained from s by removing dummy elements so that the remaining string is of length n; the remaining dummy elements are replaced by unused elements. These operations do not increase the distance. Let yoffline be the output permutation in Block Composition via Dynamic Programming, then, BlockED(y s). This inequality leads to the upper bound on the sum of disP5 offline ) ≤ BlockED(e tance i=1 ID (yoffline , πi ), completing the analysis. We analyze PostProcessing in Section 4.6, which then conclude the proof of Lemma 4.1. 22
4.3
Analysis of Windows Decomposition Step ε
Windows Decomposition constructs a set W := ∪nj=1 Wj , where Wj is defined as Wj := Wj5 ∪
5 [
Wjk−1 × S × Wj5−k .
(7)
k=1
See Section 3.2 for the full definitions of these sets. We begin by proving the existence of a pair ⟨s, e⟩ ∈ Wj that approximates the interval [αi,j , βi,j ) whenever the interval [αi,j , βi,j ) is medium. Lemma 4.2. Fix a permutation πi and an index j. If the interval [α is medium, that is, Di,j , βi,j ) E ′ , β′ αi,j + gi + ρκ < βi,j ≤ αi,j + κ/ρ, then Wj contains a pair ⟨s, e⟩ = αi,j i,j
satisfying
′ ≤α ϕi −ε , • αi,j ≤ αi,j i,j + ρn ′ ≤β . • βi,j − ρnϕi −ε − ρID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )) ≤ βi,j i,j
Proof. For notational convenience, we omit the subscript i, j in the proof. Under the assumption that ID (y ∗ , π) ≤ nϕ , we have |ℓ − α| ≤ nϕ . Since Wj contains pairs with start positions from ℓ − nϕ to ℓ + nϕ with gap g = ρnϕ−ε , one of the start position s = α′ satisfies α ≤ α′ ≤ α + ρnϕ−ε . In pairs with start position α′ , their ending positions are of the form in Equation (6). We have the following observations: • There exists an integer A1 ∈ [0, log1+ρ min( κρ , nϕ )] such that β ≤ α′ + κ + (1 + ρ)A1 . Indeed, with β in the assumption of the lemma, we have β ≤ α + κρ ≤ α′ + κρ . Additionally, as ID (y ∗ , π) ≤ nϕ , and κ = r − ℓ, it follows that β ≤ α + nϕ + κ ≤ α′ + κ + nϕ . Overall, β ≤ α′ + κ + min( κρ , nϕ ), and therefore, if we take A1 = log1+ρ min( κρ , nϕ ), then, β ≤ α′ + κ + (1 + ρ)A1 . • There exists an integer A2 ∈ [0, log1+ρ (κ(1 − ρ))] such that β ≥ α′ + κ − (1 + ρ)A2 . Indeed, with β in the assumption of the lemma, we have β ≥ α + g + ρκ ≥ α′ + ρκ. Therefore, if we take A2 = log1+ρ (κ(1 − ρ)), then, β ≥ α′ + κ − (1 + ρ)A2 . Set A = A1 if β ≥ α′ + κ, and A = A2 if β ≤ α′ + κ, then |β − α′ − κ| ≤ (1 + ρ)A . We can choose an integer a ∈ [0, A) such that (1 + ρ)a ≤ |β − α′ − κ| ≤ (1 + ρ)a+1 . Let d = ID (y ∗ [ℓ, r), π[α, β)). Since |β − α′ − κ| ≤ |β − α − κ| + |α − α′ | ≤ d + g, it follows that (1 + ρ)a ≤ d + g. We show a desired ending position β ′ by cases. • β ′ = α′ + κ if β = α′ + κ. Obviously, β ′ = β. • β ′ = α′ + κ + (1 + ρ)a ≤ β, if α′ + κ ≤ β. Observe that β − β ′ = (β − α′ − κ) − (1 + ρ)a ≤ (1 + ρ)a+1 − (1 + ρ)a = (1 + ρ)a ρ ≤ ρd + ρg ≤ ρd + g. Hence, β − ρd − g ≤ β ′ ≤ β. • β ′ = α′ +κ−(1+ρ)a+1 ≤ β, if α′ +κ ≥ β. Observe that β −β ′ = (β −α′ −κ)+(1+ρ)a+1 ≤ −(1 + ρ)a + (1 + ρ)a+1 = (1 + ρ)a ρ ≤ ρd + ρg ≤ ρd + g. Hence, β − ρd − g ≤ β ′ ≤ β. We can conclude that the pair ⟨s, e⟩ = ⟨α′ , β ′ ⟩ satisfies the conditions in the lemma. Fix an interval [ℓj , rj ) of y ∗ , we partition the set of aligned intervals {[αi,j , βi,j )}5i=1 into • Lj := {[αi,j , βi,j ) : βi,j − αi,j > κρ } the set of intervals which are large, for each i = 1, 2, . . . , 5, 23
• Nj := {[αi,j , βi,j ) : gi + ρκ ≤ βi,j − αi,j ≤ κρ } the set of intervals which are medium, for each i = 1, 2, . . . , 5, • Sj := {[αi,j , βi,j ) : βi,j − αi,j < gi + ρκ} the set of intervals which are small, for each i = 1, 2, . . . , 5. By Lemma 4.2 and the definition of Wj (Equation (7)), the following result is immediate. Corollary 4.3. For an interval [ℓj , rj ) in y ∗ and the aligned intervals [αi,j , βi,j ) in πi , there is a constructive group {π1 [s1 , e1 ), π2 [s2 , e2 ), . . . , π5 [s5 , e5 )} such that for each i = 1, 2, . . . , 5: • if [αi,j , βi,j ) is medium, then [si , ei ) satisfies the approximation condition in Equation (14), • if [αi,j , βi,j ) is small, then ⟨si , ei ⟩ ∈ S.
4.4
Analysis of Block Reconstruction Step
For any interval [ℓj , rj ) satisfying Lj = ∅ and |Nj | ≥ 4, let ANj be the constructive group ′ , β ′ )}5 . guaranteed by Corollary 4.3. We denote the strings in ANj as {πi [αi,j i,j i=1 If Lj = ∅ and |Nj | ≥ 4, we show that the output of Block Reconstruction algorithm (Algorithm 2) with input ANj gives a good approximation to y ∗ [ℓj , rj ). We introduce the following notations. ′ = π [α′ , β ′ ), and T = {π }5 , H = {π ′ }5 . Denote πi,j = πi [αi,j , βi,j ), πi,j i i,j j i,j i=1 j i,j j,i i=1 ′ ′ ′ = β′ By definition, either [αi,j , βi,j ) approximates [αi,j , βi,j ) if [αi,j , βi,j ) is medium, or αi,j i,j ′ , β ′ ) is an empty string. if [αi,j , βi,j ) is small. In the latter case, πi [αi,j i,j ′ denotes the set of elements that are in π ′ By abuse of notation, πi,j \ πi,j i,j but not in πi,j . ∗ ∗ Let Gj = G ∩ y [ℓj , rj ) and Bj = By∗ ∩ y [ℓj , rj ) be theSset of good elements and the set of ′ ). Finally, let B H be bad elements in y ∗ [ℓj , rj ), respectively. Also let Ḡj = Gj ∩ 5i=1 (πi,j \ πi,j j the set of bad elements in By∗ that appear in at least four strings in Hj . Lemma 4.4. Consider an interval [ℓj , rj ) where Lj = ∅ and |Nj | ≥ 4. Let y be the string returned by Algorithm 2 with input ANj . Then LCS(y, y ∗ [ℓj , rj )) ≥ |Gj | − 3 BjH − 4 Ḡj . e j = Gj \ Ḡj . Following from the definition of Gj Proof. Consider the subset of good elements G e j is aligned with at least 4 strings in Hj . Thus, for two distinct and Ḡj , every element a ∈ G ′ ∈ H , a and b are aligned between y ∗ [ℓ , r ) and e elements a, b ∈ Gj , for at least three strings πi,j i j j ′ πi,j . Hence, by the construction, there is a directed edge from a to b if a appears before b in y ∗ , ej . for every a, b ∈ G Observe that, for every pair of vertices a, b in the majority graph, if there is no edge between a and b, then at least one the two vertices must be either a bad element in BjH or a good element in Ḡj . e j that is After removing each pair of vertices with no edge, the number of vertices in G removed is most BjH + Ḡj . At this point, the remaining graph is a tournament. Note that, the shortest cycle in a tournament is of length 3. Moreover, in every such cycle, there is at least one vertex in BjH or a vertex in Ḡj . Thus, after iteratively removing all cycles of shortest length, e j is at most 2( B H + Ḡj ). the number of vertices removed in G j
e j least G ej − The final graph is a directed acyclic graph with the number of veritces in G 3 BjH − 3 Ḡj . As y is a topological ordering of vertices in the graph, it follows that longest e j − 3 B H − 3 Ḡj = |Gj | − common subsequence between y and y ∗ [ℓj , rj ) is greater than G j e j = |Gj | − Ḡj . 3 BjH − 4 Ḡj , where the equality is due to G
24
We count the number of elements ∗’s padded in Line 11 of Algorithm 2. Lemma 4.5. Let y be obtained from Line 11 of Algorithm 2 over the input ANj . Then, the number of dummy element ∗’s in y is at most 3 BjH + 4 Ḡj + |Bj |. Proof. Observe that the vertex set of the majority graph constructed in Line 3 of Algorithm 2 e j ∪ B T . Consequently, the algorithm initializes with a graph of at least G ej + B H contains G j j e vertices. Using the identities Gj = Gj \ Ḡj and κ = |Gj | + |Bj |, it follows that the initial size is at least κ − |Bj | − Ḡj . As in Lemma 4.4, at most 3 BjH + 3 Ḡj vertices are removed by Algorithm 2. Thus, the number of dummy elements ∗ in the final output y is at most (3 BjH + 3 Ḡj ) + Ḡj + |Bj | = 3 BjH + 4 Ḡj + |Bj | .
4.5
Analysis of Block Composition via Dynamic Programming Step
Let s be the string obtained in Block Composition via Dynamic Programming step. In this section, we give an upper bound on BlockED(s). Our strategy is to first construct a string se such that se is in the search space of Block Composition via Dynamic Programming and is close to y ∗ . This structural similarity enables us to derive an upper bound on BlockED(e s). Consequently, this yields an upper bound on the optimal cost BlockED(s) as well, since BlockED(s) ≤ BlockED(e s) by definition of s. Prior to that, we show some lemmas concerning the intervals [ℓj , rj ) with Lj ̸= ∅ or Lj = ∅ and |Sj | ≥ 2. Lemma 4.6. For each block [ℓj , rj ), if there exists i ∈ [5] such that βi,j −αi,j > κ/ρ, then setting y to be an arbitrary κ-length string satisfies that 5
5 X ID (y, y [ℓj , rj )) ≤ ρ ID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )) , 2 ∗
i=1
for any ρ ≤ 15 . Proof. Let i be an index such that βi,j − αi,j > κ/ρ. Observe that κ ID (y [ℓj , rj ), πi [αi,j , βi,j )) ≥ |(βi,j − αi,j ) − κ| > − κ = ρ ∗
1 − 1 κ. ρ
As y is an arbitrary κ-length string, it follows that, for any ρ ≤ 15 , 5ρ 1 5ρ ∗ ID (y, y [ℓj , rj )) ≤ 2κ ≤ −1 κ< ID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )) . 2 ρ 2 5 P Therefore, ID (y, y ∗ [ℓj , rj )) ≤ ρ 5i=1 ID (y ∗ [ℓj , rj ), πi [αi,j , βi,j )). 2 |By∗ | Lemma 4.7. The number of blocks [ℓj , rj ) for which |Sj | ≥ 2 is at most (1−6ρ)κ . Proof. By definition of Gj , every element a ∈ Gj is aligned between y ∗ [ℓj , rj ) with at least 4 substrings among πi,j . Since |Sj | ≥ 2 and hence |Nj | ≤ 3, every such a is aligned with at least one substring in Sj . Therefore, each element Pin Gj corresponds to at least one element in the substrings in Sj . It follows that |Gj | ≤ [αi,j ,βi,j )∈Sj (βi,j − αi,j ). For each interval 25
[αi,j , βi,j ) ∈ Sj , by definition, βi,j − αi,j < gi + ρκ ≤ 3ρκ, as gi = ρnϕi −ε ≤ 2ρκ. Thus, |Gj | ≤ 6ρκ, and |y ∗ [ℓj , rj ) \ Gj | ≥ κ − 6ρκ. Observe that y ∗ [ℓj , rj ) \ Gj ⊆ By∗ , and ∪j y ∗ [ℓj , rj ) \ Gj = By∗ , hence, the number of blocks |By∗ | [ℓj , rj ) with |Sj | ≥ 2 is at most . (1 − 6ρ)κ We partition the set of block indexes {1, 2, . . . , nε } into four subsets: • L = {j : Lj ̸= ∅}, • N = {j : Lj = ∅, |Nj | = 5}, • N ′ = {j : Lj = ∅, |Nj | = 4}, • S = {j : Lj = ∅, |Sj | ≥ 2} (note that S = {j : Lj = ∅, |Lj | ≤ 3}). A Good Estimate String. We define a string se = σ1 σ2 . . . σnε consisting of nε blocks constructed as follows. If j ∈ L ∪ S, then σj is a string of ∗ elements of length κ. If j ∈ N ∪ N ′ , then σj is the output of the Block Reconstruction algorithm (Algorithm 2) on input ANj . Lemma 4.9 below establishes a bound on the indel distance between se and y ∗ . Prior to proving Lemma 4.9, we demonstrate the following auxiliary lemma. Lemma 4.8. X
X
(|σj | − |Gj |) ≤ 5 |By∗ | + 4
j∈N ∪N ′
Ḡj .
j∈N ∪N ′
Proof. For each j ∈ N ∪ N ′ , σj is obtained from either Line 11 or Line 12 of Algorithm 2. Let tpj be the string obtained by the topological sorting performed at Line 9 of Algorithm 2. Then either σ = tp ∗κ−|tpj | (if tp < κ), or σ = tp . Hence, j
j
j
j
X
|σj | =
j∈N ∪N ′
X
j
tpj +
j∈N ∪N ′
X
κ − tpj .
j∈N ∪N ′ :|tpj |<κ
For each j ∈ N ∪ N ′ such that tpj < κ, κ − tpj is the number of padded element ∗’s in σj . By Lemma 4.5, we have κ − tpj ≤ 3 BjH + 4 Ḡj + |Bj | . Following the definition of BjH and Bj , we have that BjH ’s are mutually disjoint, and Bj ’s are mutually disjoint, for different j’s. Thus, X X κ − tpj ≤ 4 |By∗ | + 4 Ḡj . j∈N ∪N ′
j∈N ∪N ′
Since we construct tpj using only the elements in Gj and BjH , it follows that X X X |Gj | + |By∗ | , tpj ≤ |Gj | + BjH ≤ j∈N ∪N ′
j∈N ∪N ′
j∈N ∪N ′
Therefore, X
(|σj | − |Gj |) ≤ 5 |By∗ | + 4
j∈N ∪N ′
X j∈N ∪N ′
26
Ḡj .
Lemma 4.9. Let se be a string with nε blocks in which its j’th block σj is, if j ∈ L ∪ S, a string of all ∗ elements of length κ, and if j ∈ N ∪ N ′ , σj is obtained from Block Reconstruction algorithm (Algorithm 2) with input ANj , then ε
n X
∗
2
ID (σj , y [ℓj , rj )) ≤ (43.5ρ + 24ρ )
j=1
5 X
ID (y , πi ) +
1 + 12 |By∗ | . 1 − 6ρ
X
ID (σj , y ∗ [ℓj , rj )) .
∗
i=1
Proof. We decompose the left sum. ε
n X
ID (σj , y ∗ [ℓj , rj ))
j=1
=
X
ID (σj , y ∗ [ℓj , rj )) +
j∈L
X
ID (σj , y ∗ [ℓj , rj )) +
j∈N ∪N ′
j∈S
For each j ∈ L, by Lemma 4.6, we have 5
5 X ID (y ∗ [ℓj , rj ), πi,j ) . ID (e sj , y ∗ [ℓj , rj )) ≤ ρ 2 i=1
|By∗ | For j ∈ S, by Lemma 4.7, |S| ≤ (1−6ρ)κ . Hence X
ID (e sj , y ∗ [ℓj , rj )) ≤
j∈S
X
κ≤
j∈S
|By∗ | |By∗ | κ= . (1 − 6ρ)κ (1 − 6ρ)
For each j ∈ N ∪ N ′ , by Lemma 4.4, we have ID (σj , y ∗ [ℓj , rj )) = |σj | + |y ∗ [ℓj , rj )| − 2LCS(σj , y ∗ [ℓj , rj )) ≤ |σj | + κ − 2 |Gj | + 6 |Bj | + 8 Ḡj . Hence, X
ID (σj , y ∗ [ℓj , rj )) ≤
j∈N ∪N ′
X
(|σj | − |Gj |) + (κ − |Gj |) + 6 |Bj | + 8 Ḡj
j∈N ∪N ′
X
≤ 5 |By∗ | + 4
Ḡj + 7 |By∗ | + 8
j∈N ∪N ′
X
= 12 |By∗ | + 12
X
Ḡj
j∈N ∪N ′
Ḡj .
j∈N ∪N ′
P P The second inequality is due to j∈N ∪N ′ (|σj | − |Gj |) ≤ 5 |By∗ | + 4 j∈N ∪N ′ Ḡj (Lemma 4.8), Pnε P j=1 (κ − |Gj |) = |By ∗ |, and j∈N ∪N ′ |Bj | ≤ |By ∗ |. For j ∈ N , by definition of Ḡj , we have X
Ḡj ≤
5 XX
′ ′ (αi,j − αi,j ) + (βi,j − βi,j )
j∈N i=1
j∈N
≤
5 XX
2ρnϕi −ε + ρID (y ∗ [ℓj , rj ), πi,j ) .
j∈N i=1
(15)
27
For each j ∈ N ′ , let î denote the unique index such that the corresponding interval in ANj is ′ = β ′ ). Then, by the definition of Ḡ , we have empty (i.e., αî,j j î,j X X X ′ ′ (β − α ) + (αi,j − αi,j ) + (βi,j − βi,j ) Ḡj ≤ î,j î,j j∈N ′
j∈N ′
i̸=î
≤
X
g + ρκ +
X
î
j∈N ′
2ρnϕi −ε + ρID (y ∗ [ℓj , rj ), πi,j )
i̸=î
≤
j∈N
≤
X 3 ρnϕî −ε + ρID y ∗ [ℓj , rj ), π 2ρnϕi −ε + ρID (y ∗ [ℓj , rj ), πi,j ) î,j + 2 ′
X
i̸=î
5 XX
3 2ρnϕi −ε + ρID (y ∗ [ℓj , rj ), πi,j ) . 2
j∈N ′ i=1
In the second inequality, we use the assumption that βî,j − αî,j ≤ gî + ρκ. The third inequality is due to gî ≤ 2ρκ, and therefore ID y ∗ [ℓj , rj ), πî,j ≥ (rj − ℓj ) − (βî,j − αî,j ) ≥ κ − (gî + ρκ) ≥ κ − 3ρκ, which leads to ρκ ≤ 23 ρID y ∗ [ℓj , rj ), πî,j , for any ρ ≤ 19 . Combining all together, we have 5
|By∗ | 5 XX ID (y ∗ [ℓj , rj ), πi,j ) + + 12 |By∗ | ID (e s, y ) ≤ ρ 2 (1 − 6ρ) ∗
j∈L i=1
X
+ 12
5 X
ϕi −ε
2ρn
j∈N ∪N ′ i=1
3 ∗ + ρID (y [ℓj , rj ), πi,j ) 2
5 5 X 39 X 1 ρ ID (y ∗ , πi ) + 24ρ n ϕi + + 12 |By∗ | 2 1 − 6ρ i=1 i=1 5 X 1 2 ∗ + 12 |By∗ | . ≤ (43.5ρ + 24ρ ) ID (y , πi ) + 1 − 6ρ ≤
i=1
The last inequality is due to nϕi ≤ (1 + ρ)ID (y ∗ , πi ). This completes the proof. P ε As ID (e s, y ∗ ) ≤ nj=1 ID (σj , y ∗ [ℓj , rj )), the following corollary is immediate from Lemma 4.9. Corollary 4.10. ε
5 X n X
2
ID (σj , πi [αi,j , βi,j )) ≤ (1 + 217.5ρ + 120ρ )
i=1 j=1
5 X
∗
ID (y , πi ) +
i=1
5 + 60 |By∗ | . 1 − 6ρ
Proof. By the triangle inequalities, we have ε
5 X n X
ID (σj , πi [αi,j , βi,j ))
i=1 j=1 ε
≤5
n X
ε
∗
ID (σj , y [ℓj , rj )) +
j=1
≤ 1 + 217.5ρ + 120ρ2 )
5 X n X
ID (y ∗ [ℓj , rj ), πi [αi,j , βi,j ))
i=1 j=1
5 X
ID (y ∗ , πi ) + 5
i=1
28
1 + 12 |By∗ | . 1 − 6ρ
The last inequality is due to Lemma 4.9 and by definition, ID (y ∗ , πi ).
Pnε
∗ j=1 ID (y [ℓj , rj ), πi [αi,j , βi,j )) =
Bounding BlockED(e s). The string se = σ1 σ2 . . . σnε belongs to the search space defined in the step Block Composition via Dynamic Programming, as it is induced by the valid sequence of tuples (a1 , a2 , . . . , ak ), with at ∈ Cjt and indices {j1 , j2 , . . . , jk } = N ∪ N ′ . Denoting the components of the t-th tuple as at = {s, (si,t , ei,t )}5i=1 , we observe that for each i: if the interval ′ , β ′ ) approximates [α , β ). Otherwise, if the [αi,jt , βi,jt ) is medium, then [si,t , ei,t ) = [αi,j i,t i,t i,jt t interval is small, we have si,t = ei,t . The value BlockED(e s) provides an upper bound on ID (e s, πi ) corresponding to the following ), we align the block σj with the approximate in, β alignment: for every medium interval [α i,jt i,jt
′ , β ′ ) (incurring cost ID σ , π [α′ , β ′ ) ). For all other intervals, the alignment terval πi [αi,j j i i,jt i,jt i,jt t consists of deleting the block fromPse and inserting the corresponding intervals from πi . ε On the other hand, the sum nj=1 ID (σj , πi [αi,j , βi,j )) bounds ID (e s, πi ) via a slightly different alignment: for every medium interval, we align σj with the optimal interval πi [αi,j , βi,j ) (incurring cost ID (σj , πi [αi,j , βi,j ))), handling other intervals similarly as above. P P ε By triangle inequalities, BlockED(e s) approximates the sum 5i=1 nj=1 ID (σj , πi [αi,j , βi,j )) P P ′ − α ) + (β ′ ′ with an error of at most 2 5i=1 [αi,j ,βi,j ) is medium (αi,j i,j i,j − βi,j ) . As αi,j −αi,j ≤ ′ ≤ ρnϕi −ε + ρID (y ∗ [ℓ , r ), π [α , β )), we bound BlockED(e ρnϕi −ε and βi,j − βi,j s) as: j j i i,j i,j ε
BlockED(e s) ≤
5 X n X
ID (σj , πi [αi,j , βi,j )) + 4ρ
i=1 j=1
5 X
nϕi + 2ρ
i=1
5 X
ID (y ∗ , πi ) .
i=1
Finally, by applying Corollary 4.10 and the fact that nϕi ≤ (1 + ρ)ID (y ∗ , πi ), we derive the following upper bound: 5 X 5 2 ∗ BlockED(e s) ≤ (1 + 223.5ρ + 124ρ ) ID (y , πi ) + + 60 |By∗ | . 1 − 6ρ i=1
Bounding BlockED of the Output of Block Composition via Dynamic Programming Let s be the solution string obtained in step Block Composition via Dynamic Programming. Since s minimizes the objective function over the search space: s = arg min BlockED(s(aj1 , . . . , ajk )), s(aj1 ,...,ajk )
it must satisfy BlockED(s) ≤ BlockED(e s). Therefore, 2
BlockED(s) ≤ (1 + 223.5ρ + 124ρ )
5 X
ID (y , πi ) +
i=1
4.6
∗
5 + 60 |By∗ | . 1 − 6ρ
(16)
Analysis of PostProcessing Step and Proof of Lemma 4.1
Let P5 yoffline be the output permutation in the step PostProcessing. We give an upper bound for i=1 ID (yoffline , πi ), finalizing the proof of Lemma 4.1. Note that, removing element ∗’s from s and replacing remaining ∗ by unused elements in Σ to obtain yoffline does not increase the sum BlockED. Then, 5 X
ID (yoffline , πi ) ≤ BlockED(s)
i=1
≤ (1 + 223.5ρ + 124ρ2 )
5 X i=1
29
ID (y ∗ , πi ) +
5 + 60 |By∗ | . 1 − 6ρ
The last inequality is due to inequality (16). By choosing ρ = 0.000001, and the fact that |By∗ | ≤ ∆(y ∗ ) ≤ ∆(x∗ ), the above inequality becomes 5 X
ID (yoffline , πi ) ≤ 1.000225
i=1
5 X
ID (y ∗ , πi ) + 66∆(x∗ ),
i=1
completing the proof of Lemma 4.1.
4.7
From A Local Solution to A Global Median
In this section, we derive inequality (5) of Lemma 3.1 from Lemma 4.1. Specifically, let yoffline be the output obtained from ScalableMedianReconstruct algorithm with input π1 , π2 , . . . , π5 , we show that ∗
ID (yoffline , x ) ≤ 0.0009
5 X
ID (x∗ , πi ) + 266∆(x∗ ).
(5)
i=1
Proof of Lemma 3.1. Our starting point is a characterization of the distance between any two permutations x, y in terms of the quantities ∆(x) and ∆(y), specifically, ID (x, y) ≤ |Bx |+|By | ≤ ∆(x) + ∆(y). This inequality follows from the more general result for weighted Ulam metric, which we prove in Section 5.4 (Lemma 5.7). It follows, ID (yoffline , x∗ ) ≤ |Byoffline | + ∆(x∗ ). It remains to bound |ByofflineS |. By definition, Byoffline = 1≤i<j≤5 (Iπyioffline ∩ Iπyjoffline ), thus |Byoffline | ≤
X 1≤i<j≤5
=
5 X
X
Iπyioffline ∩ Iπyjoffline ≤
Iπyioffline + Iπyjoffline − ID (πi , πj )
1≤i<j≤5
ID (yoffline , πi ) + ID (yoffline , πj ) − ID (πi , πj )
i=1
(applying Lemma 4.1, and for brevity, let ρ′ = 0.000225) X ≤ (1 + ρ′ )(ID (y ∗ , πi ) + ID (y ∗ , πj )) − ID (πi , πj ) + 4 · 66∆(x∗ ) 1≤i<j≤5 ∗
= ∆(y ) + 4ρ
′
5 X
ID (y ∗ , πi ) + 264∆(x∗ )
i=1
≤ 4ρ′
5 X
ID (x∗ , πi ) + 265∆(x∗ ).
i=1
The last inequality is due to ∆(y ∗ ) ≤ ∆(x∗ ) (see inequality (2)), and by the fact that P 5 ∗ i=1 ID (x , πi ). It follows that ID (yoffline , x∗ ) ≤ ∆(x∗ ) + |Byoffline | ≤ 4ρ′
5 X
ID (x∗ , πi ) + 266∆(x∗ ).
i=1
As ρ′ = 0.000225, we obtain ID (yoffline , x∗ ) ≤ 0.0009 30
P5
∗ ∗ i=1 ID (x , πi ) + 266∆(x ).
P5
∗ i=1 ID (y , πi ) ≤
5
New Approximation Algorithms for Weighted Rank Aggregation
In this section we prove Property 2 for each metric space. We show that for Hamming, Kendalltau and Spearman’s footrule, r = 3, and for the Ulam metric r = 5. Using Theorem 2.2 we then obtain the following result. Theorem 5.1. Algorithm 1 provides a: • (1.75 + O(δ))-approximation for the 1-median problem in (Sn , distw H ) and (Sn , distF ) in linear time. • (1.9 + O(δ))-approximation for the 1-median problem in (Sn , distw τ ) in O (n log n) time. 17 . • (1.9677 + O(δ))-approximation for the 1-median problem in (Sn , distw U ) in O n Ulam and Kendall-tau analysis. The analysis for Ulam and Kendall-tau metrics requires additional notation to handle unaligned elements and pairs. For any x, p ∈ Sn , we denote by Ipx the set of unaligned characters of x with p. For the Ulam metric, these are unaligned characters of x with respect to some alignment between p and x, while in the Kendall-tau case, Ipx represents the set of unaligned pairs. We also establish a relationship between Ipx ∩ Iqx and the respective distances, in distw τ and distw . For any set S of elements (characters or pairs), we use ∥S∥ to denote the sum of weights U of elements in S. Proposition 5.2. For every p, q, x ∈ Sn , ∥Ipx ∩ Iqx ∥ ≤ dist(p, x) + dist(q, x) − dist(p, q), w Where dist is either distw τ or distU .
Proof. We have ∥Ipx ∩ Iqx ∥ = ∥Ipx ∥ + ∥Iqx ∥ − ∥Ipx ∪ Iqx ∥. Whereas, Ipx ∪ Iqx is the set of unmatched elements in either p or q, hence, ∥Ipx ∪ Iqx ∥ ≥ dist(p, q).
5.1
Hamming
For the weighted Hamming distance, we design a majority-based algorithm for subsets Q of size 3. Algorithm 4 constructs a consensus permutation by assigning the majority element to each position where one exists among the three input permutations. Positions without majority agreement are filled arbitrarily using the remaining unassigned elements. Algorithm 4 operates in linear time and space complexity. To verify correctness, observe that its output y constitutes a valid permutation since no element can simultaneously be a majority in two distinct positions. We now proceed to demonstrate that the weighted Hamming distance satisfies Property 2. Lemma 5.3. For the metric space (Sn , distw H ), any subset Q ⊆ Sn of size 3, and any local ∗ ∗ solution y obtained using Algorithm 4, we have distw H (x , y) ≤ ∆ . Proof. By definition of weighted Hamming distance: ∗ distw H (x , y) =
1 2
n X k=1 x∗ [k]̸=y[k]
31
w(x∗ [k]) + w(y[k])
(17)
Algorithm 4: Majority-based median for weighted Hamming Input : Q of size 3 Output: Local solution y ∈ Sn 1 Initialize U ← [n] // Set of unassigned elements 2 for each position k ∈ [n] do 3 if there exists element e appearing at position k in at least 2 permutations in Q then 4 Set y[k] ← e 5 Remove e from U else Mark position k as unresolved
6 7
8 for each unresolved position k (in arbitrary order) do
Assign y[k] to any element from U Remove the assigned element from U
9 10
11 return y
Denote Q = {π1 , π2 , π3 }, then, the total slack is: X ∗ w ∗ w ∆∗ = (distw H (x [k], πi [k]) + distH (x [k], πj [k]) − distH (πi [k], πj [k]))
(18)
1≤k≤n, 1≤i<j≤3 ∗ w ∗ w For the slack expression distw H (x [k], πi [k]) + distH (x [k], πj [k]) − distH (πi [k], πj [k]) at ∗ position k, we consider two cases. When πi [k] = πj [k] = e and x [k] ̸= e, this expression equals w(x∗ [k]) + w(e). When πi [k], πj [k], x∗ [k] are three distinct elements, this expression equals w(x∗ [k]). By Algorithm 4, position k is either resolved (has majority) or unresolved (no majority). We can bound the slack as: X X ∆∗ ≥ w(x∗ [k]) + w(y[k]) + w(x∗ [k]) k resolved x∗ [k]̸=y[k]
k unresolved x∗ [k]̸=y[k]
For unresolved positions where x∗ [k] ̸= y[k], note that y[k] must appear at some unresolved position k ′ in x∗ . This means y[k ′ ] ̸= x∗ [k ′ ] for some unresolved position k ′ . Hence, X k unresolved x∗ [k]̸=y[k]
w(x∗ [k]) =
1 2
X
w(x∗ [k]) + w(y[k])
k unresolved x∗ [k]̸=y[k]
Since resolved positions directly contribute w(x∗ [k]) + w(y[k]) to the slack when x∗ [k] ̸= y[k], and unresolved positions contribute sufficient slack through the pairing argument, we have: ∗ ∆∗ ≥ distw H (x , y)
5.2
Spearman’s footrule
For the Spearman’s footrule distance, we design a position-wise median algorithm for subsets Q of size 3. Algorithm 5 operates in two phases: first, it computes a pseudo-permutation z by taking the median element at each position independently among the three input permutations, second, since z may not constitute a valid permutation due to potential duplicate elements, it 32
Algorithm 5: Position-wise median for Spearman’s footrule Input : Q of size 3 Output: Local solution y ∈ Sn 1 Initialize pseudo-permutation z of length n 2 for each position k ∈ [n] do 3 z[k] ← median(Q, k) // median element at position k // Convert pseudo-permutation to valid permutation 4 Let S = {(z[k], k) : k ∈ [n]} // Element-position pairs 5 Sort S by element value to get S ′ = {(e1 , k1 ), (e2 , k2 ), . . . , (en , kn )} 6 for i = 1 to n do 7 y[ki ] ← i // Assign rank i to position ki 8 return y
converts z to a valid permutation by sorting the element-position pairs and reassigning ranks according to the sorted order of elements. Algorithm 5 operates in linear time and space complexity as the sorting step can be implemented using counting sort. Observe that the output y is a valid permutation as the sorting step ensures each element from [n] appears exactly once. The algorithm minimizes position-wise Spearman’s footrule distances in the first phase, then finds the closest valid permutation in the second phase. We use the following simple rearrangement inequality (a special case of more general results in Day [14]) to establish our results. Lemma 5.4 (Day [14]). If a1 ≤ a2 ≤ . . . ≤ an and b1 ≤ b2 ≤ . . . ≤ bn , then, n X
|ak − bk | = min
k=1
π∈Sn
n X
|ak − bπ(k) |.
k=1
From Lemma 5.4, we obtain that y is the closest permutation to the pseudo-permutation z. distF (z, y) = min distF (z, x) x∈Sn
(19)
To show that the Spearman’s footrule distance satisfies Property 2, we bound the distance from any permutation to z. Lemma 5.5. For every x ∈ Sn , distF (x, z) ≤ 21 ∆(x). Proof. Denote Q = {π1 , π2 , π3 }, without loss of generality let πi [k] be the median element at position k, that is z[k] = πi [k]. Also, let πj [k], with j ̸= i, be the element such that x[k] ≤ πi [k] ≤ πj [k] or x[k] ≥ πi [k] ≥ πj [k]. Consider again the expression distF (x, πi [k]) + distF (x, πj [k]) − distF (πi [k], πj [k]) at position k. By our selection of i, j we get that this expression equals 2 distF (x[k], πi [j]) = 2 distF (x[k], z[k]). Therefore, 1 X distF (x[k], z[k]) ≤ distF (x, πi [k]) + distF (x, πj [k]) − distF (πi [k], πj [k]). 2 1≤i<j≤3
Summing over all positions, n
1X distF (z, x) ≤ 2
X
k=1 1≤i<j≤3
1 distF (x, πi [k]) + distF (x, πj [k]) − distF (πi [k], πj [k]) = ∆(x). 2
Combining Lemma 5.5 and Equation 19, with the triangle inequality, we have 1 1 distF (x∗ , y) ≤ distF (x∗ , z) + distF (z, y) ≤ ∆∗ + ∆∗ = ∆∗ . 2 2 33
5.3
Kendall-tau
For the weighted Kendall-tau distance, we propose an algorithm that constructs a tournament graph and solves the resulting feedback arc set problem. The algorithm builds a majority graph GQ with vertex set [n], where a directed edge (a, b) exists if element a precedes element b in at least two of the three input permutations from Q. Each edge (a, b) is assigned weight 1 2 (w(a) + w(b)). To solve the feedback arc set problem on GQ , we employ the KWIK-SORT algorithm, which provides a 2-approximation guarantee when edge weights satisfy the triangle inequality [2]. This algorithm runs in O (n log n) time and uses linear space [21]. For x ∈ Sn , define Bx as the set of element pairs that are unaligned when comparing x with at least two permutations from Q = {π1 , π2 , π3 }, [ (Iπxi ∩ Iπxj ). Bx = 1≤i<j≤3
Note that for a pair of elements {a, b} where a precedes b in permutation x, we have {a, b} ∈ / Bx if and only if a precedes b in the majority of permutations from Q. Also, using Proposition 5.2, we have ∥Bx∗ ∥ ≤ ∆∗ , where ∥Bx∗ ∥ denotes the sum of weights of elements in Bx∗ . Since x is a valid permutation, we can transform GQ into an acyclic graph by redirecting edges of total weight at most ∥Bx ∥. Moreover, every orientation of the edges that transforms GQ into an acyclic graph corresponds to a permutation. This is precisely the feedback arc set problem, where the optimal solution has cost at most ∥Bx∗ ∥. As the weights in the graph satisfy the triangle inequality, the algorithm returns a permutation y that is obtained by redirecting a set of edges By with ∥By ∥ ≤ 2∥Bx∗ ∥ ≤ 2∆∗ . Lemma 5.6. For the metric space (Sn , distw τ ), any subset Q ⊆ Sn of size 3, and any local ∗ ∗ solution y obtained using the KWIK-SORT algorithm over GQ , we have distw τ (x , y) ≤ 3∆ . Proof. If both x∗ and y agree with the majority of permutations on pair {a, b}, then clearly x∗ and y agree on pair {a, b}. Hence, if x∗ and y disagree on pair {a, b}, then {a, b} ∈ By or {a, b} ∈ Bx∗ . Therefore, ∗ ∗ distw τ (x , y) ≤ ∥Bx∗ ∪ By ∥ ≤ ∥Bx∗ ∥ + ∥By ∥ ≤ 3∥Bx∗ ∥ ≤ 3∆ .
5.4
Ulam
Analogously to the Kendall-tau case, we construct a tournament graph GQ , however in this case we use Q of size 5. For the weighted Ulam distance, similar to [11], we solve the resulting feedback vertex set problem and obtain a directed acyclic graph (DAG). We return the topological order of the remaining DAG and append the removed feedback vertices arbitrarily to the end of the resulting permutation. Note that the weights are now assigned to the vertices. To solve this we use the 2-approximating feedback vertex set algorithm of Lokshtanov et al. [32]. This is a randomized algorithm that runs in time O n17 . For x ∈ Sn , define Bx as the set of elements that are unaligned when comparing x with at least two permutations from Q = {π1 , π2 , π3 , π4 , π5 }, [ Bx = (Iπxi ∩ Iπxj ). 1≤i<j≤5
Again, using Proposition 5.2, ∥Bx ∥ ≤
X
∥Ii ∩ Ij ∥ ≤ ∆(x).
1≤i<j≤5
34
(20)
If we remove the vertices in Bx from the graph GQ we get a DAG. To see this, consider any two vertices in the remaining graph, say a, b. Since each of a and b is aligned with at least 4 permutations, both a and b are aligned in at least 3 permutations. Hence, the edge between a and b corresponds to the order of a and b in x. Since x is a permutation, the remaining graph is a DAG. We now show that the weighted Ulam distance satisfies Property 2. Similar ideas were used in [11], however, we extend the proof for every two permutations in Sn . Lemma 5.7. For every x, y ∈ Sn , distw U (x, y) ≤ ∆(x) + ∆(y). Proof. Let Gx = [n] \ Bx , (resp. Gy ), is the set of elements that are aligned in at least 4 permutations. For every pair of elements a, b ∈ Gx , in at least three permutations from Q both a, b are matched. Thus, the elements in Gx form a subsequence in x such that the relative order of every a, b ∈ Gx must be consistent with their majority order across the permutations in Q (resp. for Gy ). Consequently, the relative order of every two a, b ∈ Gx ∩ Gy must match the majority order in Q. It follows that Gx ∩ Gy corresponds to a common subsequence of x and y. Therefore, distw U (x, y) ≤ ∥Bx ∪ By ∥ ≤ ∥Bx ∥ + ∥By ∥ ≤ ∆(x) + ∆(y) The last inequality follows from Equation 20. Since the local solution is a 2-approximation we get that its cost is at most twice that of an optimal solution for Q which is at most 2∆∗ . Together with Lemma 5.7, we obtain Property 2 ∗ ∗ with r = 5 and C = 3, namely, distw U (x , y) ≤ 3∆ .
6
MPC Implementation
In this section, we present the implementation of our framework (Algorithm 1) within theMPC e n1−ε for a model. We work in the sublinear regime, where the local memory per machine is O constant ε ∈ (0, 1). The set of elements and the set of positions, each represented by {1, 2, . . . , n}, is partitioned into nε subsets Σ1 ∪Σ2 ∪· · ·∪Σnε , where Σi = {(i−1)nε +1, (i−1)nε +2, . . . , inε }. When sampling permutations, we assign nε machines for each permutation. The positions of the elements in Σi and the elements located in the positions in Σi of each permutation are stored on their i’th machine. Implementing ScalableMedianReconstruct in MPC yields a (2 −α)-approximation algoe n1+6ε total space. rithm for the Ulam 1-median problem with O (1) rounds and O Theorem 1.1. For any constants δ > 0, ε ∈ (0, 1/8),there exists a polynomial-time MPC algorithm that, given a set of m permutations P ⊆ Sn , computes, with high probability, a (2 − α+O (δ))-approximation to the 1-median under the Ulam distance, where α > 0 is a constant.The e n1+6ε , and requires O e n1−ε algorithm uses O (1) communication rounds, has total space O local memory per machine. We also demonstrate the applicability of our framework to weighted settings. We implement the algorithms for computing local solutions under element-weighted Hamming, Spearman’s footrule, and Kendall-tau distances. Theorem 1.2. For any constant δ > 0, and ϵ ∈ (0, 1), there is a polynomial time MPC algorithm that, given a set of m permutations P ⊆ Sn , with high probability computes the following: • (1.75 + O (δ)) approximation of 1-median under Spearman’s footrule distance and elemente (nϵ ) processors each weighted Hamming distance using O (1) communication rounds, and O with O n1−ϵ local memory. 35
• (1.9+O (δ)) approximation of 1-median under element-weighted Kendall-tau distance using 2ϵ 1−ϵ e O (1) communication rounds, and O n processors each with O n local memory. We first present MPC implementations of algorithms that produce local solutions for Ulam, weighted Hamming, Spearman’s footrule, and weighted Kendall-tau distances. We then implement the complete framework in the MPC model using these local solution algorithms as subroutines.
6.1
Finding a local solution under Ulam distance in MPC
We implement the offline ScalableMedianReconstruct algorithm in the MPC model. We proceed in four phases. Phase 1 (Windows Decomposition and Block Reconstruction) For each j ∈ {1, 2, . . . , nε }, and for each tuple of five windows ({s1 , e1 }, {s2 , e2 }, . . . , {s5 , e5 }) ∈ Wj , we assign one machine with input consisting of: j, (π1 [s1 , e1 ), π2 [s2 , e2 ), . . . , π5 [s5 , e5 )), and (⟨s1 , e1 ⟩ , ⟨s2 , e2 ⟩ , . . . , ⟨s5 , e5 ⟩). This machine runs Block Reconstruction algorithm on its input to obtain a candidate block y = Block Reconstruction ({πi [si , ei )}5i=1 ). The output of this machine is the tuple ! 5 X j, y, ⟨s1 , e1 ⟩ , ⟨s2 , e2 ⟩ , . . . , ⟨s5 , e5 ⟩ , ID (y, πi [si , ei )) . i=1
Phase 2 (Block Composition via Dynamic Programming) the output of every machine in Phase 1 is collected in one machine. We group these outputs based on the value of j, forming sets C1 , C2 , . . . , Cnε . These sets allows us to run Algorithm 3 on this machine exactly the same as in the offline setting. Let answer be the output computed by this machine. Phase 3 (Traceback) The output answer obtained in Phase 2 implicitly defines a sequence of nε blocks. Each block corresponds to either a candidate block generated by the Block Reconstruction algorithm in Phase 1, or a dummy block consisting of κ dummy elements. We reconstruct this sequence by backtracking via the array P , starting from answer.P . This process identifies the machines from Phase 1 responsible for the computed blocks. Additionally, we allocate new machines to generate the required blocks of dummy elements. The union of these machines, denoted by Ms , collectively stores the intermediate string s. Phase 4 (PostProcessing) In this phase, we transform s into the output permutation y MPC by simulating the PostProcessing step of the offline algorithm. This involves two operations: removing the leftmost ∗ elements until the length of s reduces to n, and replacing the remaining ∗ elements with distinct unused elements in increasing order. We simulate the first operation in constant rounds. We first compute the total number of ∗ elements to be removed using a constant-depth broadcast tree. Then, also using a broadcast tree of constant depth, we ensure that each machine in Ms learns exactly how many of its own ∗ elements must be removed. Let s′ be the resulting string, distributed across the machine set Ms′ . It remains to replace the remaining ∗ positions in s′ with unused elements. We employ two sets of auxiliary machines: Mi1 to manage unused elements in Σi , and Mi2 to manage unassigned positions within the range Σi . The machines in Ms′ send all used elements belonging to Σi to Mi1 . Each machine Mi1 can then identify the complementary set of unused elements. We first determine the global position of every block in s′ . This is achieved by computing the prefix sum of block lengths via a broadcast tree. With this offset information, machines in 36
Ms′ identify the global indices of their ∗ elements and send these positions to the corresponding machines Mi2 . Finally, we assign the unused elements to the unassigned positions. Although the lists in Mi1 and Mi2 are locally sorted, the number of elements in machine Mi1 may not be the same as the number of positions in machine Mi2 . To resolve this, we compute the rank of each unused element (relative to all unused elements) and each unassigned position (relative to all unassigned positions) using a constant-depth broadcast tree. An element and a position sharing the same rank k are then paired: specifically, the element is routed to the machine in Ms′ that holds the position of rank k, completing the permutation. Lemma 6.1. The ScalableMedianReconstruct algorithm can be implemented in MPC model in O (1) rounds, using O n1−ε memory per machine and O n7ε log8 n machines. Proof. It is clear from the algorithm description that the algorithm runs in O (1) rounds. Next, we justify the memory per machine. In Phase 1, the input of each machine j; π1 [s1 , e1 ), π2 [s2 , e2 ), . . . , π5 [s5 , e5 ); {s1 , e1 }, {s2 , e2 }, . . . , {s5 , e5 } is of size O (κ), since [si , ei ) is a window of size at most O (κ). The algorithm Block Reconstruction (Algorithm 2) can be implemented with O (κ) memory. In the output of each machine, ! 5 X j, y, {s1 , e1 }, {s2 , e2 }, . . . , {s5 , e5 }, ID (y, πi [si , ei )) , i=1
P5
computing the distance i=1 ID (y, πi [si , ei )) can be done with O (κ) memory. Storing the output requires O (log n) memory. Thus, each machine in Phase 1 uses O (κ) = O n1−ε memory. In Phase 2, the machine collects the outputs of all machines in Phase 1, each with size 8 7ε O (log n). Since there are O n log n tuples in W (see Section 3.2), the number of machines used in Phase 1 is O n7ε log8 n . Thus, the total size of the input collected by the machine 9 9 7ε 7ε 1−ε in Phase 2 is O n log n . With ε < 1/8, we have O n log n = O n . Running Algo 1−ε memory. rithm 3 requires O n7ε log9 n memory. Thus, the machine in Phase 2 uses O n It is obvious that each machine in Phase 3 and Phase 4 uses O n1−ε memory. Overall, the MPC ScalableMedianReconstruct algorithm uses O n1−ε memory per machine. Next, we argue about the number of machines used. The number of machines in Phase 1 is O n7ε log8 n . We only use only one machine in Phase 2. In Phase 3 and Phase 4, the number of machines used is O (nε ). Thus, the total number of machines used is O n7ε log8 n .
6.2
Finding a local solution under Hamming distance in MPC
We simulate Algorithm 4 in the MPC model. To facilitate this, we allocate an additional nε machines to store the local solution. Assigning the majority element to each position (if one exists) is straightforward. It remains to fill out the positions without majority agreement with the unused elements. For each i, we introduce two additional machines: Mi1 , which stores unused elements in Σi , and Mi2 , which stores unassigned positions in Σi . In the first round, Mi sends unused elements to Mi1 , and unassigned positions to Mi2 . Since we just need to provide a one-to-one mapping from the list of unused elements to the list of unassigned positions, in an arbitrary manner, we can apply the filling strategy described in Phase 4 (Section 6.1). e (n) total Lemma 6.2. Algorithm 4 can be implemented in MPC model in O (1) rounds, using O space. 37
6.3
Finding a local solution under Spearman’s footrule distance in MPC
We simulate Algorithm 5 in the MPC model. Similar to implementation under Hamming distance, we allocate an additional nε machines to store the local solution. Computing the median element at each position is straightforward; however, the resulting string z may contain repeated elements and thus might not be a valid permutation. To obtain a valid permutation, Algorithm 5 sorts the entries of z and assigns the sorted entries to positions 1, 2, . . . , n in increasing order. The newly assigned values are mapped back to the original positions. To implement this step in the MPC model, we use a standard sorting algorithm in the MPC model [18] to sort all entries of z in increasing order. This sorting ensures that every entry in machine Mi is less than every entry in machine Mi+1 , and can be completed in a constant number of rounds. The final step is to map these sorted entries to the set {1, 2, . . . , n} in increasing order. This assignment is analogous to the process used for Hamming distance, where unused elements are matched to unassigned positions. It can also be accomplished in e (n) total space. O (1) rounds using O e (n) total Lemma 6.3. Algorithm 5 can be implemented in MPC model in O (1) rounds, using O space.
6.4
Finding a local solution under Kendall-tau distance in MPC
For Kendall-tau distance, we apply the KWIK-SORT algorithm to solve the feedback arc set problem on the majority graph induced by Q. In this graph, every vertex corresponds to an element, and there is a directed edge from vertex a to vertex b if a precedes b in at least two permutations from Q. In our MPC implementation, edges do not need to be stored explicitly; determining the direction of an edge between two elements requires only accessing their positions in the three permutations of Q. The KWIK-SORT algorithm starts with a random pivot, partitions the remaining vertices according to the direction of the edges to the pivot, and recurses on the resulting sets. To simulate this in constant rounds, we adapt the constant-round MPC implementation of KWIK-SORT from [21], in which multiple pivots are selected per round to form a decision tree that partitions the vertices into multiple sets for parallel recursion. Unlike [21], where O n1/2 e pivots are chosen per round due to O (n) local space, our local space constraint allows only 1−ε O n pivots. However, since partition sizes cannot be too large [21, Lemma 7], choosing Ω(log(n)) pivots per round suffices to maintain constant total rounds. Furthermore, by storing edges implicitly via element positions, we keep the total space at O (n), satisfying the local and total space constraints. Lemma 6.4. Computing a local solution under Kendall-tau distance can be implemented in e (n) total space. MPC model in O (1) rounds, using O
6.5
Implementing Algorithm 1 in MPC
Let us first review Algorithm 1, which will be simulated by our MPC algorithm. The algorithm first samples a set of O (log(n)/δ) permutations from the input set P , and includes these permutations in a candidate set C. Then, for each subset Q of r permutations sampled uniformly at random from the input set P , we find a local solution from Q, and add this solution to C. Recall that r is a constant that will be chosen depending on the specific metric. Finally, we sample a set S of O log(n)/δ 2 permutations from P , and return the permutation x ∈ C with the smallest cost(x, S). Algorithm 6 presents our MPC implementation of this algorithm. In Algorithm 6, from Line 1 to Line 6, we simulate the step of establishing a candidate set C and sampling an evaluation set S in Algorithm 1. From Line 7 to Line 12, we simulate the
38
Algorithm 6: A general MPC framework for median permutations. Input : Set P = {p1 , p2 , . . . , pm } ⊆ X , constants r, δ. Output: A permutation. 1 C ← a set of O (log(n)) permutations sampled uniformly at random from P . 2 for i = 1, 2, . . . , O (log(n)/δ), in parallel do 3 Qi ← a set of r permutations sampled uniformly at random from P . 4 yi ← localAlg(Qi ) 5 C ← C ∪ {yi } 6 Sample a set S of O log(n)/δ 2 permutations uniformly at random from P . 7 Index every permutation in C by Idxx and s ∈ S by Idxs . 8 foreach (x, s) ∈ C × S, in parallel do 9 Compute dist(x, s). 10 foreach x ∈ C, in parallel do 11
Compute cost(x, S) =
P
s∈S dist(x, s).
12 return Idxx such that x = arg minx∈C cost(x, S).
step of identifying a candidate that achieves a (1 + δ)-approximation to the best candidate in C in Algorithm 1. Let Rℓ and Sℓ be the number of rounds and spaces required to find a local solution from a set of r permutations. Denote by SD the spaces required to compute the distance between two permutations in Sn in O (1) rounds. We now analyze the round and space complexity of Algorithm 6. Space complexity. The candidate set C is initialized with O (log(n)) permutations in Line 1, and after Line 5, it is complemented with O (log n) local solutions. Storing C hence acquires a total space of O (n log n). Each execution of MPC algorithm for producing a local solution in Line 4 uses a total space of Sℓ . Since from Line 2 and Line 5, we run the this algorithm for O (log n) subsets of size r in parallel, we use a total space of Sℓ log n in these steps. Storing a sampled set of size O log n/δ 2 in Line 6 then requires O (n log n) total space. e (log n) permuWe analyze the space used from Line 7 to Line 12. As both C and S have O tations, we can uniquely index every permutation x ∈ C and s ∈ S using identifiers Idxx and Idxs respectively. The length of each index is logarithmic in the set size. In parallel, for each pair (x, s) ∈ C × S, we assign a total space of SD for (x, s) and compute e SD log2 n . their distances in O (1) rounds. This results in a total space of O Finally, for each x ∈ C, in parallel, we can use a broadcast tree of constant depth to compute cost(x, S) using O (n log n) space . Using the same argument, it is possible to find the permutation x ∈ C with the smallest cost(x, S) using O (n log n) space. e log2 (n) · SD + log(n) · Sℓ + n log(n) . Therefore, the total space used by Algorithm 6 is O Round Complexity. Each execution of MPC algorithm for producing a local solution in Line 4 runs in Rℓ rounds. Since all executions of this algorithm are done in parallel from Line 2 and Line 5, these steps take O (1) rounds. All the other steps of the algorithm also run in O (1) rounds. Therefore, the total round complexity of Algorithm 6 is Rℓ . Proof of Theorem 1.1. We apply Algorithm 6 with r = 5 and in place of localAlg in Line 4, we use the MPC implementation of ScalableMedianReconstruct algorithm.
39
From Lemma 6.1, we can compute a local solution under Ulam distance in Rℓ = O (1) 1+6ε e rounds, using Sℓ = O n total space. The Ulam distance between two permutations can be e n1+ε by approximated to within a factor of 1 + λ in O (1) rounds, with a total space of SD = O using the MPC algorithm for computing edit distance proposed in [19]. Therefore, our algorithm e n1+6ε . runs in O (1) rounds and uses a total space of O To analyze the approximation ratio, note that Algorithm 6 is a direct simulation of Algorithm 1, and the local solution algorithm used in Line 4 produces the same output as the offline ScalableMedianReconstruct algorithm. Hence, our algorithm achieves a (2−α)-approximation for Ulam 1-median problem. Proof of Theorem 1.2. We apply Algorithm 6 with r = 3 and the MPC implementations of local solution algorithms presented in Section 6.2, Section 6.3, and Section 6.4 for Hamming, Spearman’s footrule, and Kendall-tau distances respectively. For weighted Hamming and Spearmans’s footrule distances, from Lemma 6.2 and Lemma 6.3, e (n) total space. The we can compute a local solution in Rℓ = O (1) rounds, using Sℓ = O Hamming and Spearman’s footrule distances between two permutations can be computed exactly in O (1) rounds, using SD = O (n) total space. Therefore, our algorithm runs in O (1) rounds e (n) for both Hamming and Spearman’s footrule 1-median problems. and uses a total space of O For weighted Kendall-tau distance, from Lemma 6.4, we can compute a local solution in e (n) total space. The Kendall-tau distance between two Rℓ = O (1) rounds, using Sℓ = O e n1+ε total space. permutations can be computed exactly in O (1) rounds, using SD = O e n1+ε for KendallTherefore, our algorithm runs in O (1) rounds and uses a total space of O tau 1-median problem. As Algorithm 6 is a direct simulation of Algorithm 1, and the MPC algorithms for producing local solutions are straightforward implementations of their offline counterparts, our achieves the same approximation ratios as those in Theorem 5.1.
References [1] Stein Aerts, Diether Lambrechts, Sunit Maity, Peter Van Loo, Bert Coessens, Frederik De Smet, Leon-Charles Tranchevent, Bart De Moor, Peter Marynen, Bassem Hassan, et al. Gene prioritization through genomic data fusion. Nature biotechnology, 24(5):537–544, 2006. 1, 4 [2] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1–23:27, 2008. 1, 9, 34 [3] Noga Alon. Ranking tournaments. SIAM Journal on Discrete Mathematics, 20(1):137–142, 2006. 1 [4] Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 574–583. ACM, 2014. doi: 10.1145/2591796.2591805. URL https://doi.org/10.1145/ 2591796.2591805. 1, 3 [5] Christian Bachmaier, Franz J Brandenburg, Andreas Gleißner, and Andreas Hofmeier. On the hardness of maximum rank aggregation problems. Journal of Discrete Algorithms, 31: 2–13, 2015. 1 [6] Linas Baltrunas, Tadas Makcinskas, and Francesco Ricci. Group recommendations with rank aggregation and collaborative filtering. In Proceedings of the fourth ACM conference on Recommender systems, page 119–126, 2010. 1 40
[7] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. J. ACM, 64(6):40:1–40:58, 2017. doi: 10.1145/3125644. URL https://doi. org/10.1145/3125644. 1, 3 [8] Therese Biedl, Franz J Brandenburg, and Xiaotie Deng. On the complexity of crossings in permutations. Discrete Mathematics, 309(7):1813–1823, 2009. 1 [9] Kevin Buchin, Anne Driemel, and Martijn Struijs. On the hardness of computing an average curve. In SWAT, volume 162 of LIPIcs, pages 19:1–19:19. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2020. 5 [10] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the ulam metric. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, pages 761–775, 2021. 1, 5 [11] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Clustering permutations: New techniques with streaming applications. In ITCS, volume 251 of LIPIcs, pages 31:1– 31:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 1, 4, 5, 6, 9, 34, 35 [12] Yuxin Chen and Changho Suh. Spectral mle: Top-k rank aggregation from pairwise comparisons. In International Conference on Machine Learning, pages 371–380, 2015. 1 [13] Vincent A Cicirello. Classification of permutation distance metrics for fitness landscape analysis. In International Conference on Bio-inspired Information and Communication, pages 81–97. Springer, 2019. 1 [14] Peter W Day. Rearrangement inequalities. Canadian Journal of Mathematics, 24(5):930– 943, 1972. 33 [15] Persi Diaconis and Ronald L Graham. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society Series B: Statistical Methodology, 39(2):262–268, 1977. 1 [16] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of the Tenth International World Wide Web Conference, pages 613–622, 2001. 1 [17] Nick Fischer, Elazar Goldenberg, Mursalin Habib, and Karthik C. S. Hardness of median and center in the ulam metric. In ESA, volume 351 of LIPIcs, pages 111:1–111:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. 1 [18] Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Takao Asano, Shin-Ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, editors, Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings, volume 7074 of Lecture Notes in Computer Science, pages 374–383. Springer, 2011. doi: 10.1007/ 978-3-642-25591-5\_39. URL https://doi.org/10.1007/978-3-642-25591-5_39. 1, 3, 38 [19] MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. Massively parallel approximation algorithms for edit distance and longest common subsequence. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1654–1672. SIAM, 2019. 9, 40 [20] Gary Hoppenworth, Jason W Bentley, Daniel Gibney, and Sharma V Thankachan. The fine-grained complexity of median and center string problems under edit distance. In 28th Annual European Symposium on Algorithms, ESA 2020, 2020. 5 41
[21] Sungjin Im and Mahshid Montazer Qaem. Fast and Parallelizable Ranking with Outliers from Pairwise Comparisons. In Ulf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, and Céline Robardet, editors, Machine Learning and Knowledge Discovery in Databases, pages 173–188. Springer International Publishing, 2020. ISBN 978-3-030-46150-8. doi: 10.1007/978-3-030-46150-8_11. 11, 34, 38 [22] Piotr Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 428–434, 1999. 9, 13 [23] Piotr Indyk. High-dimensional computational geometry. stanford university, 2001. 9, 13, 15 [24] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 1719, 2010, pages 938–948. SIAM, 2010. doi: 10.1137/1.9781611973075.76. URL https: //doi.org/10.1137/1.9781611973075.76. 1, 3 [25] John G Kemeny. Mathematics without numbers. Daedalus, 88(4):577–591, 1959. 1 [26] Maurice G Kendall. A new measure of rank correlation. Biometrika, 30(1-2):81–93, 1938. 1 [27] Claire Kenyon-Mathieu and Warren Schudy. How to rank with few errors. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 95–103, 2007. 1 [28] Raivo Kolde, Sven Laur, Priit Adler, and Jaak Vilo. Robust rank aggregation for gene list integration and meta-analysis. Bioinformatics, 28(4):573–580, 2012. 1 [29] Caitlin Kuhlman and Elke Rundensteiner. Rank aggregation algorithms for fair consensus. Proceedings of the VLDB Endowment, 13(12), 2020. 1 [30] Ravi Kumar and Sergei Vassilvitskii. Generalized distances between rankings. In Proceedings of the 19th International Conference on World Wide Web, pages 571–580, 2010. 1 [31] Haoming Li, Sujoy Sikdar, Rohit Vaish, Junming Wang, Lirong Xia, and Chaonan Ye. Minimizing time-to-rank: A learning and recommendation approach. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 1408–1414, 2019. 1 [32] Daniel Lokshtanov, Pranabendu Misra, Joydeep Mukherjee, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. 2-approximating feedback vertex set in tournaments. ACM Trans. Algorithms, 17(2):11:1–11:14, 2021. 34 [33] Jan Pomikálek, Miloš Jakubíček, and Pavel Rychlý. Building a 70 billion word corpus of English from ClueWeb. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC’12), pages 502–506. European Language Resources Association (ELRA), 2012. URL https://aclanthology.org/L12-1624/. 1, 4 [34] V Yu Popov. Multiple genome rearrangement by swaps and by element duplications. Theoretical computer science, 385(1-3):115–126, 2007. 1 [35] Marc Sevaux and Kenneth Sörensen. Permutation distance measures for memetic algorithms with population management. In Proceedings of 6th Metaheuristics International Conference, MIC 2005, pages 832–838. University of Vienna, 2005. 1 [36] Charles Spearman. The proof and measurement of association between two things. The American Journal of Psychology, 15(1):72–101, 1904. URL http://www.jstor.org/ stable/1412159. 1 42
[37] Charles Spearman. Footrule for measuring correlation. British Journal of Psychology, 2(1): 89, 1906. 1 [38] Ryuichi Takanobu, Tao Zhuang, Minlie Huang, Jun Feng, Haihong Tang, and Bo Zheng. Aggregating e-commerce search results from heterogeneous sources via hierarchical reinforcement learning. In The World Wide Web Conference, pages 1771–1781, 2019. 1, 4 [39] H Peyton Young. Condorcet’s theory of voting. American Political science review, 82(4): 1231–1244, 1988. 1 [40] H Peyton Young and Arthur Levenglick. A consistent extension of condorcet’s election principle. SIAM Journal on applied Mathematics, 35(2):285–300, 1978. 1
43