The non-metric k-median problem
For the non-metric $k$-median problem, we can show a stronger inapproximability result than $O(\log n)$. The following is a stronger claim:
Main Claim: The non-metric $k$-median problem can not be approximated to any factor better than $n^{c}$, for any constant $c&gt;0$.
Proof:
The proof follows from the reduction from the hardness of the max $k$ coverage problem. Given a universe set $U = \{1,\dotsc,n\}$ and subsets $S_{1}, \dotsc,S_{m}$ of $U$. It is NP-hard to distinguish between the following instances:

Yes Instances: There are some $k$ sets $S_{t_{1}},\dotsc,S_{t_{k}}$ that covers all elements in $U$.

No Instances: There does not exists any $k$ sets in $S_{1}, \dotsc,S_{m}$ that can cover more than $(1-\frac{1}{e}) \cdot |U|$ elements of $U$.



Reduction: Using an instance of the max $k$ coverage, we construct a $k$-median instance $(L,C)$ as follows. A location in $L$ corresponds to a subset $S_{i}$. And, a client in
$C$ corresponds to an element $e_{j}$. Let $f_{i} \in L$ denote a
location corresponding to $S_{i}$, and $x_{j} \in C$ denote a client
corresponding to an element $e_{j} \in U$. The distance between
$f_{i}$ and $x_{j}$ is $1$ if $e_{j} \in S_{i}$ and $\Delta$
otherwise. Here $\Delta$ is some value $\gg 1$.

Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a Yes Instance.
Completeness: We open facilities at the locations that corresponds to $S_{t_{1}}, \dotsc,S_{t_{k}}$. The cost of every client to the closest facility would be exactly $1$ since every element belongs to some $S_{t_{i}}$. Therefore, the $k$-median cost is at most $|U|$.
Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a No Instance.
Soundness: No matter where we open $k$ facilities, there always exist at least $\frac{1}{e} \cdot |U|$ elements that are left uncovered. In other words, there are at least $\frac{1}{e} \cdot |U|$ clients at a distance of $\Delta$ from any open facility. Therefore, the $k$-median cost is at least $\Delta \cdot \frac{1}{e} \cdot |U|$
The completeness and soundness analysis imply that the non-metric $k$-median problem can not be approximated to any factor better than $\Delta \cdot \frac{1}{e}$. Here, we can set $\Delta$ to any arbitrary large value $\gg n^{c}$ for any constant $c&gt;0$. This completes the proof of the main claim.

Note that I could not find the above result in any literature. However, the above reduction is similar to the one used by Guha and Khuller where they take a distance of $1$ if $e_{j} \in S_{i}$ and $3$ otherwise. Using it they show the hardness of approximation for the metric facility location problem and other related problems.