  The use of online user traces for studies of human mobility has received
significant attention in recent years. This growing body of work, and the more
general importance of human migration patterns to government and industry,
motivates the need for a formalized approach to the computational modeling of
human mobility - in particular how and when individuals change their place of
residence - from online traces. Prior work on this topic has skirted the
underlying computational modeling of residence inference, focusing on migration
patterns themselves. As a result, to our knowledge, all prior work has employed
heuristics to compute something like residence histories. Here, we formalize
the residence assignment problem, which seeks, under constraints associated
with the minimum length-of-stay at a residence, the most parsimonious sequence
of residence periods and places that explains the movement history of an
individual. Here we provide an exact solution for this problem and establish
its algorithmic complexity. Because the calculation of optimal residence
histories (under the assumptions of the model) is tractable, we believe that
this method will be a valuable tool for future work on this topic.
