Find The "Best" Permutation of Inputs to Maximize Sum of Functions (or approximate "best")

Question

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.

Answer 1

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.