Robust-Sorting and Applications to Ulam-Median

Our result on robust sorting has interesting implications for another well-studied problem, namely the Ulam-$k$-Median problem. Given a positive integer $d$, let $[d]$ denote the set $\{1,\mathrm{\dots },d\}$ and ${\mathrm{\Pi }}^d$ the set of all permutations over $[d]$. We can define a metric $\mathrm{\Delta }$ over ${\mathrm{\Pi }}^d$ as follows: given ${\sigma }_1,{\sigma }_2$, $\mathrm{\Delta }({\sigma }_1,{\sigma }_2)≔d-|\text{lcs}({\sigma }_1,{\sigma }_2)|$, where $\text{lcs}({\sigma }_1,{\sigma }_2)$ denotes the length of the longest common subsequence between ${\sigma }_1$ and ${\sigma }_2$. The metric $({\mathrm{\Pi }}^d,\mathrm{\Delta })$ is also popularly known as the Ulam metric. An instance of this problem is specified by a subset $S\subseteq {\mathrm{\Pi }}^d$ and an integer $k$. The goal is to find a subset $F$ of $k$ permutations in ${\mathrm{\Pi }}^d$ (which may not lie in $S$) such that the objective value

is minimized. In other words, it is the $k$-median problem where the metric is given by $\mathrm{\Delta }$ on ${\mathrm{\Pi }}^d$. When $k=1$, there is a simple 2-approximation algorithm (which works for any metric): output the best point in the input set $S$.

Breaking the approximation guarantee of $2$ for specific metrics, such as the Ulam metric, was open for a long time. Recently, a sequence of works [5, 6] breaks this 2-factor barrier for the Ulam $k$-median problem. The algorithm is a fixed parameter tractable (FPT) algorithm (with respect to the parameter $k$) that gives an approximation guarantee of $(2-\delta )$ for a very small but fixed constant $\delta >0$. The running time of this algorithm is ${(k\log nd)}^{O(k)}n{d}^3$, which can be written as $f(k)\cdot poly(nd)$ and hence is FPT time. Note that the running time is super-linear in $n$ and cubic in $d$. This contrasts with several FPT approximation algorithms for the $k$-median/means problems in the literature [16, 13, 3, 2, 11] that have linear running time in the input size. For example, the running time of the FPT $(1+\epsilon )$-approximation algorithms for the Euclidean $k$-median/means problems in [16, 13, 3, 2] is linear in $nd$, where $d$ is the dimension. Similarly, the running time for the FPT constant factor approximation algorithms [11] in the metric setting is linear in $n$. Thus, we ask:

Is it possible to break the barrier of 2-approximation for the Ulam $k$-median problem using an FPT algorithm with a linear running time in the input size, i.e., $nd$ ?

We show that the answer is affirmative using two crucial ideas, one of which relies on the robust sorting problem. We build on the ideas of [6] for designing a $(2-\delta )$-approximation for the 1-median problem. They show that for any input set $S$, there exist five permutations ${\sigma }_1,\mathrm{\dots },{\sigma }_5$ in $S$ from which we can find a permutation $\tilde{\sigma }$ that has a small distance with respect to the optimal ${\sigma }^{\ast }$. To obtain linear in $n$ dependence on the running time, we show that a constant size randomly sampled subset of input permutations contains these five permutations with high probability. To obtain linear dependence on $d$, given guesses ${\sigma }_1,\mathrm{\dots },{\sigma }_5$ for the five permutations, we can assign each pair of symbols $(a,b)$ a direction based on the majority vote among these permutations. Now, it turns out that a good solution to the corresponding robust sorting instance is close to the optimal solution ${\sigma }^{\ast }$.

We are given a set of $n$ elements $V$. There is an (unknown) total order $\pi$ over $V$. However, we have imperfect access to the total order $\pi$. We are given an implicit directed graph $G=(V,E)$, where we have a directed edge between every pair of elements in $V$ (such graphs are often denoted tournaments). In the ideal (zero error) scenario, the edge set $E$ would correspond to $\pi$, i.e., for every distinct pair $u,v\in V$, we have the directed arc $(u,v)$ iff $u$ comes before $v$ in $\pi$. However, we allow the graph $G$ to represent $\pi$ in an imperfect manner as formalized below:

In other words, if $G$ is $B$-imperfect w.r.t. $\pi$, then the arcs with both end-points outside $B$ represent $\pi$ correctly, but we cannot give any guarantee for arcs incident with vertices in $B$. We shall often ignore the reference to $\pi$ if it is clear from the context. For edge $(u,v)\in E$, we will sometimes use the notation or $v>u$. Note that the relations are not transitive, except when $|B|=0$. Similarly, we will sometimes say that $u$ is lesser than (resp. greater than) $v$ if $(u,v)\in E$ (resp. $(v,u)\in E$).

The Robust Sort problem is as follows: given a set of points $V$ with an implicit total order $\pi$, and a query access to the edges in a tournament $G$, output an ordering $\tilde{\pi }$ on $V$ which maximizes $\text{lcs}(\pi ,\tilde{\pi })$ while using as few queries to $G$ as possible. Here $\text{LCS}(\pi ,\tilde{\pi })$ denotes the longest common subsequence between $\pi$ and $\tilde{\pi },$ and $\text{lcs}(\pi ,\tilde{\pi })$ denotes the length of $\text{LCS}(\pi ,\tilde{\pi })$. Observe that when $G$ is $0$-imperfect w.r.t. $\pi$, one can obtain the total order $\pi$ with $O(n\log n)$ queries to $G$.

The Robust Sort problem can be reduced to the well-studied Feedback Vertex Set problem on tournaments (FVST). A feedback vertex set in a directed graph is a subset of vertices whose removal makes the graph acyclic. The Feedback Vertex Set in Tournaments (FVST) problem is to find a feedback vertex set of the smallest size in a given Tournament graph. If we are allowed to query all the edges in $G$, then an $\alpha$-approximation algorithm for FVST can be utilized to obtain an $(\alpha +1)$-approximation algorithm for Robust Sort as follows: find an $\alpha$-approximate feedback vertex set $B^{\prime }$ and then find a topological ordering ${\pi }_1$ on $V\setminus B^{\prime }$. Output the concatenation $\tilde{\pi }$ of any arbitrary ordering on $B^{\prime }$ with ${\pi }_1$. Clearly, $\text{LCS}(\pi ,\tilde{\pi })\ge |{\pi }_1|-|B|=|V|-|B^{\prime }|-|B|\ge |V|-(\alpha +1)|B|.$ Hence, using exponential time, we can find an optimal feedback vertex set and therefore a $2$-approximate solution to Robust Sort. However, since feedback vertex set on tournaments is NP-hard to approximate better than a factor of $2$, and a polynomial time 2-approximation algorithm is known [17], $3$-approximation is the best we can get from such a direct reduction to FVST. Indeed, consider a simple example where $V=\{v_1,v_2,v_3,v_4\}$, $\pi =(v_2,v_1,v_3,v_4),B=\{v_2\}$. Consider a $B$-imperfect tournament $G$, such that for all unordered pairs $(v_i,v_j)$ with , there is an arc from $v_i$ to $v_j$ in $G$, except the direction of the arc is reversed for $(v_2,v_3)$ and $(v_2,v_4)$. In this example, a $2$-approximation algorithm might return $\{v_3,v_4\}$ as the feedback vertex set. Hence, ${\pi }_1=(v_1,v_2)$ is the only topological ordering on the remaining vertices, and we might return $\tilde{\pi }=(v_4,v_3,v_1,v_2)$. Here, $\text{LCS}(\pi ,\tilde{\pi })=1=|V|-3|B|.$

Although the algorithm of Lokshtanov et al. [17] is also inspired by quick-sort, it queries $\mathrm{\Omega }(n^2)$ edges and runs in $O(n^{12})$ time. In our setting, we are constrained by near-linear running time and, hence, can only check a small subset of triangles for consistency. However, this causes several other issues: a bad pivot can masquerade as a good one, and a good pivot may not get a chance to partition the elements into almost equal halves. The fact that we are on a very tight budget in terms of the number of queries and errors makes the algorithm and analysis quite subtle.

The Ulam $k$-median problem is simply the $k$-median problem defined over the Ulam metric $({\mathrm{\Pi }}^d,\mathrm{\Delta })$ – given a set $S\subset {\mathrm{\Pi }}^d$ of $n$ elements and a positive integer $k$, find a set $C$ of $k$ elements (called centers) such that the objective function $Obj(S,C)≔{\sum }_{s\in S}{\min }_{c\in C}\mathrm{\Delta }(s,c)$ is minimized. Here, ${\mathrm{\Pi }}^d$ is the set of all permutations of $[d]≔\{1,2,3,\mathrm{\dots },d\}$, which can also be seen as all $d$-length strings with distinct symbols from set $\{1,2,\mathrm{\dots },d\}$. The distance function $\mathrm{\Delta }$ is defined as $\mathrm{\Delta }(x,y)≔d-\text{lcs}(x,y)$, where $\text{lcs}(x,y)$ denotes the length of the longest common subsequence of permutations $x,y\in {\mathrm{\Pi }}^d$. There is a trivial 2-approximation algorithm and it has been a long open challenge to obtain a better approximation. Breaking this barrier of 2 was recently achieved by Chakraborty et al. [6] who gave a parameterized algorithm (with parameter $k$) with a running time of ${(k\log nd)}^{O(k)}n{d}^3$ and approximation guarantee of $(2-\delta )$ for a small constant $\delta$. Our goal was to achieve the same using a parameterized algorithm with running time $\tilde{O}(f(k)\cdot nd)$.

We first consider ${ℱ}_1.$ Suppose $S_t$ has at least $\frac{{|S_t|}^3}{24k}$ triangles. The probability that an iteration of the for loop in lines 1.6–1.10 does not find a triangle is at most $1-\frac{1}{24k}$. Thus, the probability that none of the $72k\log N$ iterations find a triangle is at most ${\left(1-\frac{1}{24k}\right)}^{72k\log N}\le \frac{1}{N^3}.$

We now analyze the event ${ℱ}_2.$ Suppose we choose a pivot $p$ in line 1.12 which is not balanced w.r.t. $S_t$. We need to argue that we shall execute line 1.22 (which happens when $\min (|L_1|,|R_1|)\le \frac{k^{\prime }}{5}+\frac{k^{\prime }}{40}$) with high probability. Let $L$ and $R$ denote the set of elements in $S_t\setminus \{p\}$ that are lesser than and greater than $p$, respectively. Assume (the other case is similar). Thus, the expected size of $L_1$ is at most $\frac{k^{\prime }}{5}$. It follows from standard Chernoff bounds that the probability that $|L_1|>\frac{k^{\prime }}{5}+\frac{k^{\prime }}{40}$ is at most: $e^{\frac{-{\left(\frac{1}{40}\right)}^2\cdot \frac{k^{\prime }}{5}}{3}}\le e^{-4\log N}\le \frac{1}{N^4}$. Since we can execute line 1.12 at most $36\log N$ times during a particular iteration $t$ of the while loop, it follows by union bound that $\mathrm{Pr}[{ℱ}_2]\le \frac{1}{N^3}.$ (for large enough $N$).

Finally, we consider the event ${ℱ}_3$. Suppose $S_t$ has at most $|S_t|/3$ bad elements, i.e., there are at least $2|S_t|/3$ good elements. Consider the middle (in the ordering ${\pi }_g$) $|S_t|/6$ good elements of $S_t$. Any such element has at least $\frac{1}{2}\cdot (2|S_t|/3-|S_t|/6)=|S_t|/4$ good elements on either side. It follows that if the pivot $p$ is chosen among these $|S_t|/6$ elements, then the expected size of the sets $L_1,R_1$ defined in lines 1.13–1.20 is at least $\frac{k^{\prime }}{4}=(\frac{k^{\prime }}{5}+\frac{k^{\prime }}{40})+\frac{k^{\prime }}{40}$. Thus, for such a pivot, using the Chernoff bound, the probability of executing line 1.22 (that is, $\min (|L_1|,|R_1|)\le \frac{k^{\prime }}{5}+\frac{k^{\prime }}{40}$) is at most $1/4$. Hence, the probability that we do not execute line 1.35 in a particular iteration of the for loop in line 1.11 is at least $\frac{1}{6}\cdot \frac{3}{4}=\frac{1}{8}.$ Thus, $\mathrm{Pr}[{ℱ}_3]=$ the probability that we execute line 1.35 in each of the iterations of this for loop is at most ${\left(1-\frac{1}{8}\right)}^{36\log N}\le \frac{1}{N^3}.$ $◀$

Given a subset $S$ of $V$, let ${\pi }^{\prime }(S)$ be the sequence generated by $\text{ROBUST-SORT}(S)$. Note that ${\pi }^{\prime }(S)$ is a random sequence. Given integers $n$ and $b$, let $𝒮(n,b)$ denote all subsets $S$ of size $n$ of $V$ which have $b$ bad elements. Let $L(n,b)$ denote the maximum expected loss of the sequence output by Algorithm 1 when run on a subset $S\in 𝒮(n,b)$. More formally,

We now state the induction hypothesis that shall prove the main result Theorem 2:

We prove the above result by induction on $n$. When $n=1$, the result follows trivially. Now assume it is true for all $L(n^{\prime },b^{\prime }),$ where $n^{\prime }\le n-1$. Now, we would like to show it for $L(n,b)$ for some given $b\le n$. Fix a subset $S\in 𝒮(n,b)$. We need to show that

We first check an easy case.

We know by Lemma 7 that the failure event ${ℱ}_1$ happens with probability at most $1/N^3$. Thus, with probability at least $1-1/N^3$, the algorithm shall make a recursive call on a subset $S^{\prime }$ obtained from $S$ by removing a triangle $(x,y,z)$ found in line 1.9 (notice that, whenever we remove a triangle $\{x,y,z\}$, we start from scratch after setting $S\leftarrow S\setminus \{x,y,z\}$). This triangle must contain at least 1 bad element. We can assume that it has exactly one bad element (otherwise, the induction hypothesis applied on $S^{\prime }$ only gets stronger because the r.h.s. of Equation 1 is monotonically increasing with $b$). Thus, $𝐄[\text{loss}({\pi }^{\prime }(S))]\le \left(1-\frac{1}{N^3}\right)(L(n-3,b-1)+3)+\frac{n}{N^3}$, where the second term on the r.h.s. appears because the loss can never exceed $n$. Applying induction hypothesis on $L(n-3,b-1)$, we see that the above is at most

where the second inequality uses $c=\frac{ϵ}{\log N}$ and assumes that $N$ exceeds a large enough constant (for a fixed $ϵ$) $\mathrm{⊲}$ Henceforth, assume that $S$ has at most $\frac{n^3}{24k}$ triangles. Further, if the algorithm finds a triangle in line 1.9, then the same argument as above applies. Thus, we can condition on the event that no triangles are found in the for loop in lines 1.6–1.10. We can also assume that $b\le n/3$, otherwise the condition (2) follows trivially. Assume that ${ℱ}_3$ does not occur (we shall account for this improbable event later). In that case, we know that we shall find a balanced pivot $p$ of $S$ during one of the iterations of the for loop in line 1.11, and such that the condition in line 1.21 will not hold. Let $L$ and $R$ be as defined in lines 1.28–1.33. We now give a crucial definition.

Recall that, we say that $a$ is less than $b$, if $(a,b)\in E$. Using the definition of loss, it is easy to verify that $M_p=0$ if $p$ is a good element. For an element $p\in S$, let $q_p$ denote the probability that no triangles are found in the for loop in line 1.23 conditioned on the fact that $p$ is chosen in the pivot in line 1.12 and the execution reaches the for loop in line 1.23. We have the following key lemma:

We first prove the lower bound on $q_p$. Consider an element $p\in S$. The probability that during an iteration of the for loop in line 1.23, we pick the (unordered) triplet $\{x,y,p\}$ for a triangle $(x,y,p)$ is $\frac{2}{n^2}$. Since there are $T_p$ triangles containing $p$, the probability that we pick a triangle containing $p$ is at most $\frac{2T_p}{n^2}$. Thus, the probability that we do not pick any such triangle during the $k$ iterations of the for loop in line 1.23 is at least ${\left(1-\frac{2T_p}{n^2}\right)}^k.$

Now, we prove the upper bound. Assume $M_p>0$; otherwise, the claim is trivial. Let $L$ and $R$ denote the partition of $S\setminus \{p\}$ with respect to the pivot $p$. Let $X$ and $Y$ be sequences over subsets of $L$ and $R$ respectively such that $M_p=\text{concatloss}(X,Y)$. Recall that $\text{supp}(X)$ (or $\text{supp}(Y)$) is the longest common subsequence between $X$ (or $Y$) and the optimal sequence ${\pi }_g^{\star }$ on the good elements. In particular, $\text{supp}(X)$ and $\text{supp}(Y)$ consist of sorted good elements.

Let $X_1$ denote the suffix of length $M_p/2$ of $\text{supp}(X)$, and $Y_1$ denote the prefix of length $M_p/2$ of $Y$. We claim that for any $x\in X_1,y\in Y_1,(x,y,p)$ forms a triangle. Suppose not. Then, $x$ is less than $y$. But then, consider concatenating the prefix of $\text{supp}(X)$ till $x$ and the suffix of $Y$ from $y$ (see Figure 1). These sequence of good elements will be sorted and hence a subsequence of ${\pi }_g^{\star }$. But the length of this sequence is larger than $\text{supp}(X)+\text{supp}(Y)-M_p.$ This implies that a contradiction. Thus, we see that there are at least $\frac{M_p^2}{4}$ triangles involving $p$ and elements of $S\setminus \{p\}$. So, any particular iteration of the for loop in line 1.23 shall find such a triangle with probability at least $\frac{M_p^2}{4n^2}$. This proves the desired upper bound on $q_p$. $◀$

Let $\mathrm{𝖡𝖺𝗅}(S)$ denote the set of all balanced pivots of $S$, that is, the elements $p$ of $S$ for which the partition $L\cup R$ of $S\setminus \{p\}$ is balanced ($\min (|L|,|R|)\ge \frac{n}{5}$). For a pivot $p$, let $h_p$ denote the probability that, when $p$ is chosen as pivot (in line 1.12), we get a balanced partition $(L_1,R_1)$ of the sampled elements, that is, $\min (L_1,R_1)>\frac{k^{\prime }}{5}+\frac{k^{\prime }}{40}$ (and hence, line 1.22 is not executed). Recall that $b\le \frac{n}{3}$. Hence, assuming ${ℱ}_3$ does not occur, there must be some pivot, among the (up to) $36\log N$ sampled pivots, that passes the balanced partition test (i.e., line 1.22 is not executed for this pivot). Let ${\gamma }_p$ denote the probability that this pivot is $p$. It is easy to see that ${\gamma }_p=\frac{h_p}{{\sum }_{u\in S}{h}_u}$.

The first statement follows from the definition of ${ℱ}_2$ and  Lemma 7. Now, notice that for $p\in \mathrm{𝖬𝗂𝖽}(S),h_p\ge \frac{3}{4}$ (this was argued in the proof of Lemma 7 when bounding the probability of $F_3$), and ${\sum }_{p\in S}{h}_p\le n$. Hence, ${\gamma }_p\ge \frac{1}{2n}$ for all $p\in \mathrm{𝖬𝗂𝖽}(S)$. For the third statement, note that ${\sum }_{p\in S}{h}_p\ge {\sum }_{p\in \mathrm{𝖬𝗂𝖽}(S)}{h}_p\ge \frac{n}{6}\cdot \frac{1}{2}=\frac{n}{12}$. Also, $h_p\le 1$ for all $b\in B.$ Hence, ${\gamma }_p\le \frac{12}{n}$ for all $p\in B$. $◀$

Now, once a pivot $p$ passes the partition test, there are two possibilities:

1. (a)

   With probability $q_p$, we partition $S$ into $L$ and $R$ with respect to $p$ and recursively call $\text{ROBUST-SORT}(L)$ and $\text{ROBUST-SORT}(R)$. Let the output of these recursive calls be sequences ${\sigma }_L$ and ${\sigma }_R$, respectively (recall that the output of $\text{ROBUST-SORT}(L)$ or $\text{ROBUST-SORT}(R)$ can be a sequence on a subset of $L$ or $R$ respectively). Let $\sigma$ denote the concatenated sequence $({\sigma }_L,p,{\sigma }_R)$. If $p$ is a good element, then $M_p=0$, and hence $\text{loss}(\sigma )=\text{loss}({\sigma }_1)+\text{loss}({\sigma }_2)$. If $p$ is a bad element, $\text{loss}(\sigma )$ is same as the loss of the sequence $({\sigma }_1,{\sigma }_2)$. The latter quantity, by the definition of $M_p$, is at most $\text{loss}({\sigma }_1)+\text{loss}({\sigma }_2)+M_p.$ Let $L$ and $R$ have $b_L$ and $b_R$ bad elements, and let their sizes be $n_L$ and $n_R.$ For, $p\in S\setminus \mathrm{𝖡𝖺𝗅}(S),𝐄[\text{loss}(\sigma )]\le n$. For $p\in \mathrm{𝖡𝖺𝗅}(S)$,

   	$𝐄[\text{loss}(\sigma )]$	$\le 𝐄[\text{loss}({\sigma }_L)]+𝐄[\text{loss}({\sigma }_R)]+M_p$
   		$\le 3b_L+c{b}_L\log n_L+3b_R+c{b}_R\log n_R+M_p$
   		$\le 3b+cb\log \max (n_L,n_R)+M_p$
   		$\le 3b+cb\log n-cb\log (5/4)+M_p,$

   where the second inequality follows from the induction hypothesis, and the last inequality uses $\max (n_L,n_R)\le \frac{4n}{5}$.

2. (b)

   With probability $(1-q_p)$, a triangle is found in lines 1.23–1.27. In this case, we effectively recurse on a subset $S^{\prime }$ of $S$, where $S^{\prime }$ has $n-3$ elements and at most $b-1$ bad elements. In this case, the induction hypothesis implies that the expected loss of the sequence returned by $\text{ROBUST-SORT}(S)$ is, at most

   $$𝐄[{\pi }^{\prime }(S^{\prime })]+3\le 3(b-1)+c(b-1)\log (n-3)+3\le 3b+cb\log n$$

   where the expectation is over the choice of $S^{\prime }$ and the $\text{ROBUST-SORT}(S^{\prime })$ procedure.

Putting everything together, we see that (conditioned on ${ℱ}_3$ not happening),
$𝐄[\text{loss}({\pi }^{\prime }(S))|{ℱ}_3\text{ does not happen}]$ is at most (recall that $B$ is the set of bad elements):

where the first inequality uses the observation that $\mathrm{𝖬𝗂𝖽}(S)\subseteq \mathrm{𝖡𝖺𝗅}(S)\setminus B$, and utilizes the bounds on ${\gamma }_p$ derived in  Lemma 11. The second inequality uses the bounds on $q_p$ derived in  Lemma 10. Now, observe that, the expression $x{(1-x^2)}^k$ over $x>0$, is maximized at $x=\frac{1}{\sqrt{2k+1}}$, and hence,

Substituting this in (3), we see that $𝐄[\text{loss}({\pi }^{\prime }(S))|{ℱ}_3\text{does not happen}]$ is at most:

After Claim 8, we had assumed that ${sup}_p{T}_p\le \frac{n^3}{24k}$. Therefore, there can be at most $n/12$ elements for which $T_p>\frac{n^2}{2k}$. It follows that there are at least $n/6-n/12=n/12$ elements $p$ of $\mathrm{𝖬𝗂𝖽}(S)$ for which $T_p\le \frac{n^2}{2k}$. Therefore, the expression above is, at most:

where the first inequality uses the fact that $k\ge 2$ and hence, ${(1-1/k)}^k\ge 1/4$, the second one uses the fact that $c=\frac{ϵ}{\log N}$, and the last inequality assumes that $N$ exceeds a large enough constant (for a fixed $ϵ$), and $b\ge 1$ (for $b=0$, $L(n,b)=0$ trivially holds). Now,