The problem is NP-hard. Without loss of generality we shall prove this in the case that all the weights are positive integers. First let us rephrase the problem as follows.

Given an integer-valued matrix, find the reordering of the columns that maximizes the score of the resulting reordered matrix, where the score of a matrix is defined as follows: It is the sum of the scores of the rows, where the score of a row is the value of the leftmost nonzero entry in that row (or zero if the row is all zero, but clearly we may assume that there are no all-zero rows).

To see the equivalence, let the columns correspond to the vertices of $A$ and let the rows correspond to the vertices of $B$; zeros correspond to non-edges and the integers correspond to the edge weights. The following reduction from SAT to (the decision version of) the above problem is due to my colleague Sandy Kutin.

Suppose we are given a SAT instance with $m$ clauses and $n$ variables. Without loss of generality we shall assume that for each variable $x$, one of the clauses in the system is $x\vee\bar x$. We now construct a matrix with $2n+1$ columns and $m+2n$ rows as follows. For each variable $x$ we have two columns, one labeled $x$ and the other labeled $\bar x$. We also have a special column labeled $z$.

For each clause, we create a row; for each literal in the clause, we put the value $2n+2$ in the corresponding column, and we put a 1 in the $z$ column. In the other columns we put zero. This gives us the first $m$ rows. Then for each of the $2n$ literals, we create a row with a 1 in the column corresponding to that literal and a 2 in the $z$ column. Now we ask the question:

Is there a reordering of the columns with score at least $m(2n+2) + 3n$?

If the SAT instance is satisfiable, then the answer is yes: For each literal $x$ that is TRUE, put the $x$ column to the left of the $z$ column and the $\bar x$ column to the right of the $z$ column. Then we score $2n+2$ for each of the first $m$ rows and a total of $3n$ for the remaining $2n$ rows.

Conversely, in order to score as high as $m(2n+2)+3n$, we need to score $2n+2$ for each of the first $m$ rows, since scoring only $1$ for one of those rows sacrifices $2n+1$, which is more than we can make up for using the final $2n$ rows. Therefore for every clause, at least one of the literals in it must have its column to the left of the $z$ columns. To pick up an additional $3n$ from the remaining $2n$ rows, it must be the case that for each literal $x$, either the $x$ or the $\bar x$ column must appear to the *right* of the $z$ column (they cannot both appear to the right because then we would fail to score $2n+2$ from the $x\vee\bar x$ row). Thus by picking all the literals to the left of the $z$ column, we obtain a satisfying assignment.

doesmatter. If you remove a node in step 2, the weights of its incident edges are no longer available for step 3 of subsequent iterations. $\endgroup$ – Emil Jeřábek Sep 3 '14 at 9:58