Skip to main content

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.

Filter by
Sorted by
Tagged with
15 votes
1 answer

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 ...
LarrySnyder610's user avatar
33 votes
4 answers

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 ...
LarrySnyder610's user avatar