Speeding Up k-neighborhood local search in limited memory influence diagrams

Denis D. Mauá, Fabio G. Cozman

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

1 Cita (Scopus)

Resumen

Limited memory influence diagrams are graph-based models that describe decision problems with limited information, as in the case of teams and agents with imperfect recall. Solving a (limited memory) influence diagram is an NP-hard problem, often approached through local search. In this paper we investigate algorithms for k-neighborhood local search. We show that finding a k-neighbor that improves on the current solution is W[1]-hard and hence unlikely to be polynomial-time tractable. 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
Páginas (desde-hasta)334-349
Número de páginas16
PublicaciónLecture Notes in Computer Science
Volumen8754
DOI
EstadoPublicada - 2014
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Speeding Up k-neighborhood local search in limited memory influence diagrams'. En conjunto forman una huella única.

Citar esto