Questions tagged [p-median]
Questions related to p-median problems, i.e. placing $p$ facilities such that the average distance from demand nodes to the nearest facility is minimal.
2
questions
15
votes
1answer
175 views
Symmetric undirected $p$-median instance with fractional LP solution?
The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP ...
33
votes
4answers
831 views
Why are integer minimax problems hard?
Problems that have a minimax-type structure are notoriously hard to solve. For example, the $p$-median problem from facility location (choose $p$ facilities to minimize demand-weighted distance to ...