Tight Approximations for Graphical House Allocation

The Graphical House Allocation problem asks: how can n houses (each with a fixed non-negative value) be assigned to the n 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 Graphical House Allocation. 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. Some of the technical highlights of our work are the use of expansion properties of Ramanujan graphs in the context of a classical resource allocation problem, and approximating optimal cuts in binary trees by analyzing the behavior of consecutive runs in bitstrings.