  We study the set of optimal solutions of the dual linear programming
formulation of the linear assignment problem (LAP) to propose a method for
computing a solution from the relative interior of this set. Assuming that an
arbitrary dual-optimal solution and an optimal assignment are available (for
which many efficient algorithms already exist), our method computes a
relative-interior solution in linear time. Since LAP occurs as a subproblem in
the linear programming relaxation of quadratic assignment problem (QAP), we
employ our method as a new component in the family of dual-ascent algorithms
that provide bounds on the optimal value of QAP. To make our results applicable
to incomplete QAP, which is of interest in practical use-cases, we also provide
a linear-time reduction from incomplete LAP to complete LAP along with a
mapping that preserves optimality and membership in the relative interior. Our
experiments on publicly available benchmarks indicate that our approach with
relative-interior solution is frequently capable of providing superior bounds
and otherwise is at least comparable.
