# NP-hardness of euclidean Facility Location/k-median variant

The Facility Location Problem (FLP) is defined as follows:

Input: Sets C of clients and $F$ of potential facilities, opening costs $f_i$ for all $i \in F$, and connection costs c_{ij} for all $i \in F$ and $j \in C$.
Task: Choose a subset $F'$ of $F$, such that $\sum_{i \in F'} f_i + \sum_{j \in C} \min_{i \in F'} c_{ij}$ is minimal.

The FLP is NP-hard even with metric distances, for instance by a simple reduction from set cover (clients are elements, facilities are sets).

In the euclidean (or geometric) FLP clients and facilities are points in $\mathbb{R}^2$, and the $c_{ij}$ are the euclidean distances. The survey article "Approximation schemes for NP-hard geometric optimization problems: A survey" by Arora seems to claim that this variant is NP-hard as well (page 21: "All problems listed below are known to be NP-hard unless stated otherwise."), however the referenced papers neither contain nor reference this result.

Question 1: Is the euclidean FLP known to be NP-hard?

The modified problem without opening costs, but a restriction on the number of opened facilities seems to be very close to the $k$-median problem:

Input: A set $C$ of points in $\mathbb{R}^2$.
Task: Choose a set $F$ of $k$ points such that $\sum_{j \in C} \min_{i \in F} c_{ij}$ is minimal.

This problem, and the variant where $F$ has to be a subset of $C$, are known to be NP-hard (without restriction: On the complexity of some common geometric location problems, with restriction: Worst-case and probabilistic analysis of a geometric location problem).

Question 2: Is the modified problem without opening costs but with only $k$ allowed facilities known to be NP-hard?

Update: I found an answer to the second question (this problem contains the median variant with restriction as the special case where $F = C$), but am still interested in the first.