The Probabilistic k-Center Problem

Demange, M, Haddad, M and Murat, C 2018, 'The Probabilistic k-Center Problem', in Proceedings of the GEOSAFE Workshop on Robust Solutions for Fire Fighting 2018, L'Aquila, Italy, 19-20 July 2018, pp. 62-74.


Document type: Conference Paper
Collection: Conference Papers

Title The Probabilistic k-Center Problem
Author(s) Demange, M
Haddad, M
Murat, C
Year 2018
Conference name GEOSAFE Workshop on Robust Solutions for Fire Fighting
Conference location L'Aquila, Italy
Conference dates 19-20 July 2018
Proceedings title Proceedings of the GEOSAFE Workshop on Robust Solutions for Fire Fighting 2018
Publisher CEUR-WS.org
Place of publication L'Aquila, Italy
Start page 62
End page 74
Total pages 13
Abstract 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.
Subjects Optimisation
Operations Research
Analysis of Algorithms and Complexity
Keyword(s) Wildfire management
k-centre problem
probabilistic combinatorial optimisation
Versions
Version Filter Type
Access Statistics: 20 Abstract Views  -  Detailed Statistics
Created: Thu, 06 Dec 2018, 10:39:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us