  In this paper we study the {\it bilinear assignment problem} (BAP) with size
parameters $m$ and $n$, $m\leq n$. BAP is a generalization of the well known
quadratic assignment problem and the three dimensional assignment problem and
hence NP-hard. We show that BAP cannot be approximated within a constant factor
unless P=NP even if the associated quadratic cost matrix $Q$ is diagonal.
Further, we show that BAP remains NP-hard if $m = O(\sqrt[r]{n})$, for some
fixed $r$, but is solvable in polynomial time if $m = O(\sqrt{\log n})$. When
the rank of $Q$ is fixed, BAP is observed to admit FPTAS and when this rank is
one, it is solvable in polynomial time under some additional restrictions. We
then provide a necessary and sufficient condition for BAP to be equivalent to
two linear assignment problems. A closed form expression to compute the average
of the objective function values of all solutions is presented, whereas the
median of the solution values cannot be identified in polynomial time, unless
P=NP. We then provide polynomial time heuristic algorithms that find a solution
with objective function value no worse than that of $(m-1)!(n-1)!$ solutions.
However, computing a solution whose objective function value is no worse than
that of $m!n!-\lceil\frac{m}{\beta}\rceil !\lceil\frac{n}{\beta}\rceil !$
solutions is NP-hard for any fixed rational number $\beta>1$.
