  The Graphical House Allocation problem asks: how can $n$ houses (each with a
fixed non-negative value) be assigned to the vertices of an undirected graph
$G$, so as to minimize the "aggregate local envy", i.e., the sum of absolute
differences along the edges of $G$? This problem generalizes the classical
Minimum Linear Arrangement problem, as well as the well-known House Allocation
Problem from Economics, the latter of which has notable practical applications
in organ exchanges. Recent work has studied the computational aspects of
Graphical House Allocation and observed that the problem is NP-hard and
inapproximable even on particularly simple classes of graphs, such as vertex
disjoint unions of paths. However, the dependence of any approximations on the
structural properties of the underlying graph had not been studied.
  In this work, we give a complete characterization of the approximability of
the Graphical House Allocation problem. We present algorithms to approximate
the optimal envy on general graphs, trees, planar graphs, bounded-degree
graphs, bounded-degree planar graphs, and bounded-degree trees. For each of
these graph classes, we then prove matching lower bounds, showing that in each
case, no significant improvement can be attained unless P = NP. We also present
general approximation ratios as a function of structural parameters of the
underlying graph, such as treewidth; these match the aforementioned tight upper
bounds in general, and are significantly better approximations for many natural
subclasses of graphs. Finally, we present constant factor approximation schemes
for the special classes of complete binary trees and random graphs.
