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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.