  We consider the problem of locating a single facility on the real line. This
facility serves a set of agents, each of whom is located on the line, and
incurs a cost equal to his distance from the facility. An agent's location is
private information that is known only to him. Agents report their location to
a central planner who decides where to locate the facility. The planner's
objective is to minimize a "social" cost function that depends on the
agent-costs. However, agents might not report truthfully; to address this
issue, the planner must restrict himself to {\em strategyproof} mechanisms, in
which truthful reporting is a dominant strategy for each agent. A mechanism
that simply chooses the optimal solution is generally not strategyproof, and so
the planner aspires to use a mechanism that effectively {\em approximates} his
objective function. In our paper, we study the problem described above with the
social cost function being the $L_p$ norm of the vector of agent-costs. We show
that the median mechanism (which is known to be strategyproof) provides a
$2^{1-\frac{1}{p}}$ approximation ratio, and that is the optimal approximation
ratio among all deterministic strategyproof mechanisms. For randomized
mechanisms, we present two results. First, we present a negative result: we
show that for integer $\infty>p>2$, no mechanism---from a rather large class of
randomized mechanisms--- has an approximation ratio better than that of the
median mechanism. This is in contrast to the case of $p=2$ and $p=\infty$ where
a randomized mechanism provably helps improve the worst case approximation
ratio. Second, for the case of 2 agents, we show that a mechanism called LRM,
first designed by Procaccia and Tennenholtz for the special case of
$L_{\infty}$, provides the optimal approximation ratio among all randomized
mechanisms.
