  Motivated by real-world applications such as the allocation of public
housing, we examine the problem of assigning a group of agents to vertices
(e.g., spatial locations) of a network so that the diversity level is
maximized. Specifically, agents are of two types (characterized by features),
and we measure diversity by the number of agents who have at least one neighbor
of a different type. This problem is known to be NP-hard, and we focus on
developing approximation algorithms with provable performance guarantees. We
first present a local-improvement algorithm for general graphs that provides an
approximation factor of 1/2. For the special case where the sizes of agent
subgroups are similar, we present a randomized approach based on semidefinite
programming that yields an approximation factor better than 1/2. Further, we
show that the problem can be solved efficiently when the underlying graph is
treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for
the problem on planar graphs. Lastly, we conduct experiments to evaluate the
per-performance of the proposed algorithms on synthetic and real-world
networks.
