We are given a n-vertex DAG $G=(V,E)$ and also given a cost function $c: V \rightarrow \Bbb N$.
Given a topological sort $S = v_1,v_2,...,v_n$, it has associated a sorting cost $S_c = \sum_{i=1}^{n} C(v_i)$ where $C(v_i)$ is the cost of choosing $v_i$ at that point: i.e. the sum of the cost functions of all vertices that were candidates at the point of choosing $v_i$, but they weren't chosen. Obviously, precedent vertices to $v_i$ in $S$ (already chosen vertices) are not included in this sum.
The idea is to find a topological sort $S$ that minimizes $S_c$. I think its a NP-hard problem, but would there be any approximation algorithm, or at least some smart heuristic? I tried to find this exact same problem but I couldn't find it... just similar ones.