The approximation threshold for metric k-median

For every fixed ε > 0, we give a deterministic polynomial-time $(1+2/e+\epsilon )$-approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under $P\ne NP$, the infimum approximation factor in this model is therefore $1+2/e$.