The Probabilistic k-Center Problem
2018
The k-Center problem on a graph is to nd a set K of k vertices minimizing
the radius dened as the maximum distance between any vertex
and K. We propose a probabilistic combinatorial optimization model
for this problem, with uncertainty on vertices. This model is inspired
by a wildre management problem. The graph represents the adjacency
of zones of a landscape, where each vertex represents a zone. We
consider a nite set of re scenarios with related probabilities. Given a
k-center, its radius may change in some scenarios since some evacuation
paths become impracticable. The objective is to nd a robust k-center
that minimizes the expected value of the radius over all scenarios. We
study this new problem with scenarios limited to a single burning vertex.
First results deal with explicit solutions on paths and cycles, and
hardness on planar graphs.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
1
Citations
NaN
KQI