  In this work we consider general facility location and social choice
problems, in which sets of agents $\mathcal{A}$ and facilities $\mathcal{F}$
are located in a metric space, and our goal is to assign agents to facilities
(as well as choose which facilities to open) in order to optimize the social
cost. We form new algorithms to do this in the presence of only {\em ordinal
information}, i.e., when the true costs or distances from the agents to the
facilities are {\em unknown}, and only the ordinal preferences of the agents
for the facilities are available. The main difference between our work and
previous work in this area is that while we assume that only ordinal
information about agent preferences in known, we know the exact locations of
the possible facilities $\mathcal{F}$. Due to this extra information about the
facilities, we are able to form powerful algorithms which have small {\em
distortion}, i.e., perform almost as well as omniscient algorithms but use only
ordinal information about agent preferences. For example, we present natural
social choice mechanisms for choosing a single facility to open with distortion
of at most 3 for minimizing both the total and the median social cost; this
factor is provably the best possible. We analyze many general problems
including matching, $k$-center, and $k$-median, and present black-box
reductions from omniscient approximation algorithms with approximation factor
$\beta$ to ordinal algorithms with approximation factor $1+2\beta$; doing this
gives new ordinal algorithms for many important problems, and establishes a
toolkit for analyzing such problems in the future.
