1
$\begingroup$

The Problem (in words)

I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the total value of my items but I am willing to accept a "good" order if it means finding it quickly.

The Problem (in maths)

Given $N$ monotonically decreasing functions $f_i$(x) where $1 <= i, x <= N$ and a set $S = \{1, 2, 3, ..., N\}$

Find $\alpha$, a permutation of $S$ which maximizes the objective function $g(\alpha) = \sum_{i=1}^{N} f_i(\alpha(i))$

In the event that this is a hard (e.g. NP-Complete) problem, I would rather have an approximation algorithm which returns a permutation that gives some local maxima of $g$ with provable guarantees on the distance to the optimal one.

My Thoughts

I am not very familiar with optimization problems but this feels like one that should be well known. I feel that if I knew the name of it I would have been able to search it on my own.

I am able to put more constraints on $f_i$ if needed but I would prefer to allow it to be any monotonically decreasing function.

I cannot brute force this as the values of $N$ I work with lead to far too many permutations.

My initial thought was to use a greedy algorithm which chooses the highest valued remaining item starting with position 1 and iterating until position N. I know this will not produce the best result but it is possible it produces a "good enough" result. I am not comfortable with using this greedy algorithm unless I have a proof of how effective it is.

$\endgroup$
2
$\begingroup$

One approach is to view this as an instance of the assignment problem: you have a bipartite graph, with items on the left and positions on the right, and $f_i(p)$ tells you the value of matching item $i$ to position $p$, so draw an edge $i \to p$ with weight $f_i(p)$, and then find the maximum-weight bipartite matching. This will give an optimal solution. It also demonstrates that the problem can be solved in polynomial time, i.e., it is not NP-hard. The running time will be $O(n^3)$, which might be reasonable if $n$ is not too large but might be too expensive if $n$ is very large.

It might be possible to find some other algorithm that is more efficient (i.e., has faster runtime), by taking advantage of the fact that each $f_i$ is monotonically decreasing.

$\endgroup$
2
  • $\begingroup$ I was just about to post this :( $\endgroup$ – orlp Dec 15 '20 at 20:00
  • $\begingroup$ Perfect. This is exactly what I was looking for. I agree with you that the monotonicity of the functions is likely the key to making a more efficient algorithm but this is already a major step $\endgroup$ – Jake Greene Dec 15 '20 at 20:46

Your Answer

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

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