The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$.
Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is bipartite.
Proof: Assume that $G$ is bipartite with parts $L$ and $R$. Consider $\pi$ that first puts the vertices from $L$ and then the vertices from $R$ (the relative ordering of vertices in $L$ and $R$ may be arbitrary). Then the cost of this solution is $0$, as required.
Now assume that $G$ has a solution $\pi$ of cost $0$. Note that $G$ cannot have an odd cycle. Indeed if $a_1 \to a_2 \to \dots \to a_k$ is an odd cycle, then the direction of edges along the cycle should alternate: say $(a_1, a_2)$ goes forward (w.r.t. $\pi$), then $(a_2, a_3)$ goes backward, then $(a_3, a_4)$ goes forward etc (or the other way around). That is impossible since the cycle is odd. We conclude that $G$ doesn't have any odd cycles and thus is bipartite.
QED
Claim. Let $G$ be a regular graph, whose vertices have degree $d$. Denote the costs of optimal solutions of problems $\cal U$ and $\cal P$ in $G$ by $U_G$ and $P_G$, respectively. Then
$$P_G =\Theta(d\cdot U_G).$$
Proof: Let $E'$ be an optimal solution for $\cal U$ in $G$. Then $|E'| = U_G$. Let $(L, R)$ be a bipartition of $G - E'$. Consider a permutation $\pi$ defined by $L$ and $R$, as in the proof of Observation. The cost of $\pi$ is at most $d \cdot |E'| = d\cdot U_G$ (to get this, write the formula for the cost of $\pi$; upper bound $|\mathrm{succ}_{\pi}(u)|$ by $d$ for vertices in $L$; upper bound $|\mathrm{pred}_{\pi}(u)|$ by $d$ for vertices in $R$). Thus, $P_G \leq d\cdot U_G$.
Now consider an optimal solution $\pi$ for $\cal P$. For every vertex $u$, either $|\mathrm{pred}_{\pi}(u)| \leq d/2$ or $|\mathrm{succ}_{\pi}(u)| \leq d/2$. In the former case, mark edges from $u$ to $\mathrm{pred}_{\pi}(u)$ as bad; in the latter case, mark edges from $u$ to $\mathrm{succ}_{\pi}(u)$ as bad. Note that when we process $u$, we mark $\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|)$ edges. We have,
$$\min(|\mathrm{pred}_{\pi}(u)|, |\mathrm{succ}_{\pi}(u)|) \leq |\mathrm{pred}_{\pi}(u)| \times |\mathrm{succ}_{\pi}(u)| / (d/2).$$
Adding up this inequality over all $u$, we get that the total number of bad edges is at most $2P_G/d$. Now let $E'$ be the set of bad edges. Clearly, $P_{G- E'} = 0$. From Observation, we get that $G-E'$ is bipartite. Thus, $E'$ is a feasible solution for $\cal U$. We conclude that $U_G \leq 2P_G/d$.
We have proved that
$$\frac{d}{2} U_G \leq P_G \leq d\cdot U_G.$$
QED
We see that in regular graphs, $\cal P$ and $\cal U$ are essentially equivalent. Note that it was shown in
Chawla, Shuchi, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.
Sivakumar. "On the hardness of approximating Multicut and
Sparsest-cut." Computational Complexity 15, no. 2 (2006): 94-114.
that there is no constant factor approximation for $\cal U$ if the Unique Games Conjecture holds. On the other hand, there is an $O(\sqrt{\log n})$ approximation algorithm for $\cal U$; see
Agarwal, Amit, Moses Charikar, Konstantin Makarychev, and Yury
Makarychev. "$O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min
2CNF Deletion, and directed cut problems." In Proceedings of STOC 2005, pp. 573-581.
What about the regularity assumption?
The regularity assumption is not really necessary and was made above to simplify the exposition.
Hardness of approximation. We can start with any (not necessarily regular) instance $G = (V, E)$ of $\cal U$. Let $d$ be the maximum degree of $G$. Attach $d - \deg u$ new vertices to every vertex $u\in V$. We will obtain a new graph $G' = (V', E')$, in which every vertex has degree $d$ or $1$. Clearly, $U_{G} = U_{G'}$. Now we apply the reduction from Claim to $G'$. It's easy to see that the reduction still works for $G'$, even though it's not regular (since $\deg u\in\{1, d\}$ for every $u$).
Algorithm. Given an instance $G = (V, E)$ of $\cal U$, we create a weighted graph $G'$; $G' = (V, E, w)$ is the same graph as $G$ except that edge $(u,v)$ has weight
$$w(u,v) = \min(\deg u, \deg v).$$
We solve $\cal U$ in $G'$, and get a partition $(L,R)$ of $V$. We define $\pi$ as follows: first put vertices from $L$ and then vertices from $R$. Importantly, the order of vertices in $L$ and in $R$ is not arbitrary now. We put vertices with smaller degrees closer to the boundary between $L$ and $R$. (In other words, vertices in $L$ and $R$ are sorted by their degrees in the descending and ascending orders, respectively.) It's not hard to see that this algorithm gives $O(\sqrt{\log n})$ approximation.
Conclusion:
- There is no constant factor approximation for $\cal P$ if the Unique
Games Conjecture holds.
- There is an $O(\sqrt{\log n})$ approximation algorithm.
- In order to get a better approximation factor, one needs to improve the best known approximation algorithm for Min Uncut (which would be a breakthrough result in the field, especially since the problem is closely related to Sparsest Cut and Balanced Cut).
(Informal note: we will not get any better algorithms if we assume that the graph has a high average degree or a relatively low average degree.)
Generalization: The proof can be adapted in a straightforward way to this problem, where instead of looking for a permutation of the nodes, we look for an orientation of the edges (that is a less constrained problem where the edge orientation does not have to induce a DAG).
It can also be adapted in a straightforward way to the case where the objective to minimize is $\sum_{v\in V} ~\min(\left|\text{succ}_{\pi}(v)\right|,
\left|\text{pred}_{\pi}(v)\right|)$ instead of $\sum_{v\in V} ~\left|\text{succ}_{\pi}(v)\right|\times
\left|\text{pred}_{\pi}(v)\right|$. Interestingly, with that new objective we have $U_G = P_G$.
