Branch and bound for minimum linear arrangement

Question

I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.

Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , n\}$. For a permutation $f$ of the nodes of $G$, the weight of each edge $(x,y)$ will be $|f(x)-f(y)|$. The total weight of $G$ will be the sum of the weights of its edges. You can think of $f$ as a relabeling of the nodes of $G$, where $f(x)$ is the new label of node $x$.

I am trying to find a permutation $f$ that results in a minimum total weight of $G$.

Now trying to solve this, all I could come up with is finding the approximate cost that is the sum of weights of each edge completed till now (for each backtracking tree node) and proceed from the minimum cost node. I am wondering if someone can help me with a better approximation formula.