Consider an undirected graph G modelling a network. Each vertex in the graph contains some physical devices, which can be monitored and possibly repaired from a remote site in case they become faulty. We assume that there can be two kinds of faults in the system: soft faults, which can be repaired remotely from another site (i.e., a monitor), and severe faults which cannot be repaired remotely and require further (possibly human) interventions. We assume that soft faults happen with some fixed probability λ, 0 < λ ≤ 1. We investigate the problem of locating monitors in the network so as to minimize the total expected communication cost per fault. We formalize such a problem as a location problem with a cost function depending on λ and study some properties of the optimal solutions. The latter are exploited for investigating the complexity of the problem and providing efficient approximation algorithms.

On a Facility Location Problem with Applications to Tele-Diagnostic / Apollonio, N; Caramia, M; Italiano, Giuseppe Francesco. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 7:6(2013), pp. 1179-1192.

On a Facility Location Problem with Applications to Tele-Diagnostic

Italiano G
2013

Abstract

Consider an undirected graph G modelling a network. Each vertex in the graph contains some physical devices, which can be monitored and possibly repaired from a remote site in case they become faulty. We assume that there can be two kinds of faults in the system: soft faults, which can be repaired remotely from another site (i.e., a monitor), and severe faults which cannot be repaired remotely and require further (possibly human) interventions. We assume that soft faults happen with some fixed probability λ, 0 < λ ≤ 1. We investigate the problem of locating monitors in the network so as to minimize the total expected communication cost per fault. We formalize such a problem as a location problem with a cost function depending on λ and study some properties of the optimal solutions. The latter are exploited for investigating the complexity of the problem and providing efficient approximation algorithms.
Algorithm complexity; Graph algorithms; Location problems
On a Facility Location Problem with Applications to Tele-Diagnostic / Apollonio, N; Caramia, M; Italiano, Giuseppe Francesco. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - 7:6(2013), pp. 1179-1192.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/199779
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact