  We revisit the discrete heterogeneous two-facility location problem, in which
there is a set of agents that occupy nodes of a line graph, and have private
approval preferences over two facilities. When the facilities are located at
some nodes of the line, each agent derives a cost that is equal to her total
distance from the facilities she approves. The goal is to decide where to
locate the two facilities, so as to (a) incentivize the agents to truthfully
report their preferences, and (b) achieve a good approximation of the minimum
total (social) cost or the maximum cost among all agents. For both objectives,
we design deterministic strategyproof mechanisms with approximation ratios that
significantly outperform the state-of-the-art, and complement these results
with (almost) tight lower bounds.
