# Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)

## 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.

## 1 Answer

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.

• I was just about to post this :( – orlp Dec 15 '20 at 20:00
• 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 – Jake Greene Dec 15 '20 at 20:46