Fast local search methods for solving limited memory influence diagrams

Denis Deratani Mauá, Fabio Gagliardi Cozman

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)

Resumen

© 2015 Elsevier Inc. All rights reserved. Limited memory influence diagrams are graph-based models that describe decision problems with limited information such as planning with teams and/or agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this work we give a closer look at k-neighborhood local search approaches. We show that finding a k-neighboring strategy that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. We also show that finding a strategy that resembles an optimal strategy (but may have low expected utility) is NP-hard. We then develop fast schema to perform approximate k-local search; experiments show that our methods improve on current local search algorithms both with respect to time and to accuracy.
Idioma originalInglés estadounidense
Páginas (desde-hasta)230-245
Número de páginas16
PublicaciónInternational Journal of Approximate Reasoning
DOI
EstadoPublicada - 1 ene 2016
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Fast local search methods for solving limited memory influence diagrams'. En conjunto forman una huella única.

Citar esto