The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
1answer
147 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 ...
22
votes
4answers
233 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 ...