Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison matrix $M \in \mathcal P_n$ is said to be strongly stochastically transitive (SST) if $M_{ik} \ge \max(M_{ij},M_{jk})$ whenever $i,j,k$ are distinct and $\min(M_{ij},M_{jk}) \ge 1/2$. Let $\mathcal T_n \subseteq \mathcal P_n$ be the set of all SST. Given $M \in \mathcal T_n$, consider the following problem
Problem. Find $T^* \in \mathcal T_n$ such that $\Delta(M,T^*)$ is minimal, where $\Delta(M,T) := \|M-T\|_1 = 2\sum_{i < j} |M_{ij}-T_{ij}|$.
$\Delta(M,T^*)$ is just a measure of the amount of editing done on the input matrix $M$, in order to make it into an SST matrix.
Question
Is the above problem reducible to some standard problem in computer science which can be solved efficiently (i.e in time polynomial in $n$) at least apprimately, say an algorithm which returns $\widehat{T} \in \mathcal T_n$ such that $\Delta(M,\widehat{T}) \le (1+\epsilon)\Delta(M,T^*)$ ?
