
The probabilistic k-center problem
Demange, Marc; Haddad, Marcel Adonis; Murat, Cécile (2018), The probabilistic k-center problem, in Di Stefano, Gabriele; Navarra, Alfredo, Proceedings of the GEO-SAFE workshop - Robust Solutions for Fire Fighting (RSFF'18), CEUR-WS.org, p. 62-74
View/ Open
Type
Communication / ConférenceDate
2018Conference title
GEO-SAFE workshop - Robust Solutions for Fire Fighting (RSFF'18)Conference date
2018-07Conference city
L'AquilaConference country
ItalyBook title
Proceedings of the GEO-SAFE workshop - Robust Solutions for Fire Fighting (RSFF'18)Book author
Di Stefano, Gabriele; Navarra, AlfredoPublisher
CEUR-WS.org
Number of pages
103Pages
62-74
Metadata
Show full item recordAuthor(s)
Demange, Marcautre
Haddad, Marcel Adonis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Murat, Cécile
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 / Keywords
Wildfire management; k-centre problem; probabilistic combinatorial optimisationRelated items
Showing items related by title and author.
-
Haddad, Marcel Adonis; Demange, Marc; Gabrel, Virginie; Murat, Cécile (2019) Communication / Conférence
-
Demange, Marc; Gabrel, Virginie; Haddad, Marcel Adonis; Murat, Cécile (2020) Article accepté pour publication ou publié
-
Haddad, Marcel Adonis; Murat, Cécile; Demange, Marc (2019) Communication / Conférence
-
Demange, Marc; Gabrel, Virginie; Haddad, Marcel Adonis; Murat, Cécile (2019) Communication / Conférence
-
Haddad, Marcel Adonis (2020-12-14) Thèse