Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process. To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G = (V, E) with a source vertex s, stochastic edge costs drawn from a distribution πe, e ∈ E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied. Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Ω(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(log nR) resource augmentation suffices to obtain O(1) approximation on trees and O(log nR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process - the minesweeper problem - which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(log nR) approximation for general graphs. We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1 + budget, whose adaptivity gaps on trees and general graphs are 1 + and 8 + , respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.

Stochastic graph exploration / Anagnostopoulos, A.; Cohen, I. R.; Leonardi, S.; Lacki, J.. - 132:(2019). (Intervento presentato al convegno 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 tenutosi a Patras; Greece) [10.4230/LIPIcs.ICALP.2019.136].

Stochastic graph exploration

Anagnostopoulos A.
;
Cohen I. R.
;
Leonardi S.
;
Lacki J.
2019

Abstract

Exploring large-scale networks is a time consuming and expensive task which is usually operated in a complex and uncertain environment. A crucial aspect of network exploration is the development of suitable strategies that decide which nodes and edges to probe at each stage of the process. To model this process, we introduce the stochastic graph exploration problem. The input is an undirected graph G = (V, E) with a source vertex s, stochastic edge costs drawn from a distribution πe, e ∈ E, and rewards on vertices of maximum value R. The goal is to find a set F of edges of total cost at most B such that the subgraph of G induced by F is connected, contains s, and maximizes the total reward. This problem generalizes the stochastic knapsack problem and other stochastic probing problems recently studied. Our focus is on the development of efficient nonadaptive strategies that are competitive against the optimal adaptive strategy. A major challenge is the fact that the problem has an Ω(n) adaptivity gap even on a tree of n vertices. This is in sharp contrast with O(1) adaptivity gap of the stochastic knapsack problem, which is a special case of our problem. We circumvent this negative result by showing that O(log nR) resource augmentation suffices to obtain O(1) approximation on trees and O(log nR) approximation on general graphs. To achieve this result, we reduce stochastic graph exploration to a memoryless process - the minesweeper problem - which assigns to every edge a probability that the process terminates when the edge is probed. For this problem, interesting in its own, we present an optimal polynomial time algorithm on trees and an O(log nR) approximation for general graphs. We study also the problem in which the maximum cost of an edge is a logarithmic fraction of the budget. We show that under this condition, there exist polynomial-time oblivious strategies that use 1 + budget, whose adaptivity gaps on trees and general graphs are 1 + and 8 + , respectively. Finally, we provide additional results on the structure and the complexity of nonadaptive and adaptive strategies.
2019
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Approximation algorithms; Graph exploration; Stochastic optimization
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Stochastic graph exploration / Anagnostopoulos, A.; Cohen, I. R.; Leonardi, S.; Lacki, J.. - 132:(2019). (Intervento presentato al convegno 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 tenutosi a Patras; Greece) [10.4230/LIPIcs.ICALP.2019.136].
File allegati a questo prodotto
File Dimensione Formato  
Anagnostopoulos_Stochastic-Graph-Exploration_2019.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 534.91 kB
Formato Adobe PDF
534.91 kB Adobe PDF

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: https://hdl.handle.net/11573/1344488
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact