1
$\begingroup$

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^*)$ ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.