6
$\begingroup$

Let $A$ be an $n \times k$ matrix of real numbers.

I'm looking for an exact algorithm to find a permutation of the rows of $A$, in such a way that the total number of inversions found in the resulting $k$ column vectors is minimal. That is, if $B$ is a row-wise permutation of $A$, I want to minimize:

$$ L(B) = \sum _{j = 1} ^k \iota (B ^ j),$$

where $\iota(x)$ is the number of inversions in the array $x$, and $B^j$ denotes the $j$-th column of $B$.

I tried to do some basic research on the topic, but could not find anything particularly relevant. The $k=1$ special case amounts to simple array sorting, and I'm hoping one could generalize some array sorting algorithm to this more general case.

Any hint and/or reference would be very appreciated, thanks!

Side note: in the special application I have in mind, $n$ is small (around $100$), so that any solution with time complexity less than, say, $2^n$, could work for all practical purposes.)

$\endgroup$

1 Answer 1

1
$\begingroup$

While I do not have an answer, I have given this some thought and would like to share my ideas.

I am making two simplifying assumptions but the general case shouldn't be much harder.

  1. All numbers are distinct on each column.
  2. $k$ is odd.

Now let $c_{i,j}$ be the number of inversions caused by putting row $i$ above row $j$; that is, the number of columns $l$ for which $A_{i,l} > A_{j,l}$. For the rest of the argument, we can ignore $A$ and work with the matrix $c$. Due to assumption 1, $c_{i,j} + c_{j,i} = k$ for all row pairs. Furthermore, due to assumption 2, $c_{i,j} \neq c_{j,i}$ and exactly one of the two will be smaller than $k/2$. When $c_{i,j} < k/2$, we say that row $i$ dominates row $j$.

Domination among rows can be cyclical as illustrated by the three rows below. Row 1 dominates row 2 (columns 1, 2 and 3 have smaller elements, thus $c_{1,2} = 2$ and $c_{2,1} = 3$), row 2 dominates row 3 and row 3 dominates row 1. Note that, for every pair of rows $i$ and $j$, either $i$ dominates $j$ or viceversa. You can view this as a tournament graph with $n$ nodes.

(1 1 2 3 3)
(2 2 3 1 2)
(3 3 1 2 1)

The task with these notations is to find a permutation of rows $\pi$ which minimizes

$$ \sum_{i<j} c_{\pi(i), \pi(j)}$$

Let us consider what happens if we swap two consecutive elements, $\pi(i)$ and $\pi(i + 1)$. Those elements do not move relative to the other $n-2$, only relative to one another. The total cost changes by

$$ -c_{\pi(i),\pi(i+1)} + c_{\pi(i + 1),\pi(i)} = \\ -c_{\pi(i),\pi(i+1)} + (k - c_{\pi(i),\pi(i + 1)}) = \\ k - 2 \cdot c_{\pi(i),\pi(i + 1)} $$

Since $\pi$ is optimal, it follows that the swap must increase the cost, hence

$$ c_{\pi(i),\pi(i + 1)} < k/2 $$

, in other words row $\pi(i)$ dominates row $\pi(i + 1)$. This holds for every consecutive pair of rows in the permutation. It follows that, if any of the $n$ rows dominates all the others, then no other rows may come before it in $\pi$. It must necessarily be placed first and we can reduce the problem by one row.

This is where I got stuck. If all the rows are part of a cycle in the tournament graph mentioned above, I do not know how to break the tie. Still, the following backtracking algorithm might perform well, depending on how adversarial your data is.

Assume we have filled $\pi(1...i-1)$. If there exists a row that dominates all the remaining rows, place it at position $i$ and recurse. Otherwise, from the remaining rows, iterate among those dominated by $\pi(i-1)$. Place each of them at position $i$ and recurse. Some heuristic might be useful here to prune the backtracking more quickly. For example, we could consider rows in increasing order of

$$\sum_{j \in \mbox{ remaining rows }} c_{i,j}$$

Keep a running cost of the permutation so far. If at any point it exceeds the minimum cost found so far, go back one level.

$\endgroup$
3
  • 1
    $\begingroup$ Very interesting, I was making the two very same assumptions for preliminary study. Assumption 1 is absolutely OK, let's assume (say) each column of $A$ is a permutation of ${1, ..., n}$. Assumption 2 is annoying, but good for a start. I'll need some time to go carefully through your answer, thanks for taking the time to share your thoughts! $\endgroup$
    – pppqqq
    Commented Jun 21, 2022 at 13:09
  • 1
    $\begingroup$ The graph theory point of view is very interesting, we basically want a Hamiltonian path in the tournament which minimizes the sum of back edge weights. If I correctly understand the introductory remarks of this paper (cse.buffalo.edu/faculty/atri/papers/algos/FAS-journal-final.pdf), it seems like we've hit a NP-hard problem. $\endgroup$
    – pppqqq
    Commented Jun 22, 2022 at 7:18
  • 2
    $\begingroup$ Nice find! Time for that bittersweet feeling when you give up hope for a polynomial algorithm, but at least you can focus on finding a decent exponential algorithm... I would give a shot to generating all the permutations, pruning early when exceeding the best solution so far and iterating each level from the most dominating node to the least one. $\endgroup$ Commented Jun 22, 2022 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.