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 &quot;best&quot; order for these items is the one that maximizes the total value of my items but I am willing to accept a &quot;good&quot; order if it means finding it quickly.
The Problem (in maths)
Given $N$ monotonically decreasing functions $f_i$(x) where $1 &lt;= i, x &lt;= 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 &quot;good enough&quot; result. I am not comfortable with using this greedy algorithm unless I have a proof of how effective it is.
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.