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
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
Version Filter Type
Access Statistics: 30 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