Approximately sorting integers by many criteria

Question

Given $k$ functions $f_0, f_1...f_k$, a large dataset of size $n$, is there an algorithm that will "approximately" sort the dataset according to all of the functions so that "most" items of the dataset end up close to where they should be if they were sorted by any one of the functions alone.

More formally, if we have the functions $R_k(i)$ which gives the rank of item $i$ if the dataset were sorted with $f_k$, and $R'(i)$ which gives the actual rank of the item, we can define the statistic: $$r_k = 1 - \frac{6\sum_{i=0}^n{(R'(i) - R_k(i))^2}}{n(n^2-1)}$$ (this is the Spearman rank correlation coefficient of the actual against predicted positions)

Is there an algorithm which will increase the total $r = \sum_{i=0}^k{r_i^2}$, either by outright maximising $r$, or some kind of convergent process which can increase $r$ to its maximum?

Obviously, sorting according to just one of the functions will give $r > 0$ but can we do better than this?

I am not really concerned with running time, but anything better than the naive $O(n!)$ of going through all the permutations and computing $r$ would be good.

The motivation for this is to improve branch prediction while searching a large dataset without using any extra space.

Answer 1

I don't know if there is an efficient algorithm that will always produce the optimal solution. I would suggest looking at heuristics that hopefully will often work well, even if they don't come with guarantees. One plausible approach would be to use simulated annealing, or some other form of local search. At any point, you can pick a pair of random indices $i,j$ and consider would happen to $r$ if you swap the items at those two locations; then the simulated annealing algorithms describes the conditions under which you apply that swap vs not. Repeat until convergence. There are no guarantees this will give the global optimum -- it get stuck in a local optimum -- but it could be worth a try.

---

If you are OK with maximizing $\sum_i r_i$ instead of maximizing $\sum_i r_i^2$, the following might work. You might be able to reduce this to the assignment problem and then apply a standard algorithm for the assignment problem. In particular, for each item $i$ and each rank $j \in \{0,1,2,\dots,n\}$ create an edge from item $i$ to rank $j$ whose cost is $\sum_k 6(j-R_k(i))^2/n(n^2-1)$. Then, use an algorithm for the assignment problem to find an assignment that assigns a unique rank to each item. The sum of the costs of the selected edges will be equal to $k-\sum_i r_i$, so minimizing the sum of the costs will maximize $\sum_i r_i$. Assigning each item to a unique rank is equivalent to sorting the items; you just put the items in order of their rank. The assignment problem ensures that no two items will receive the same rank, and every item will receive some rank.

I'm not sure if this works or not. At one point I thought this would work; then at another point I thought it wouldn't work (but I can't remember why not); and now I'm thinking again that this should work, and give a polynomial-time algorithm to find the exact solution for maximizing $\sum_i r_i$. As you can see, I've gotten myself totally mixed up here, so I don't trust my thought process. Double-check all of my reasoning here before placing any reliance on it. (Even if this doesn't give the optimal answer, it's also possible that it provides a useful initialization for simulated annealing.)