Speeding up k-neighborhood local search in limited memory influence diagrams. 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-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.
Keywords for this software
References in zbMATH (referenced in 3 articles , 1 standard article )
Showing results 1 to 3 of 3.
- Mauá, Denis Deratani: Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams (2016)
- Mauá, Denis Deratani; Cozman, Fabio Gagliardi: Fast local search methods for solving limited memory influence diagrams (2016)
- Mauá, Denis D.; Cozman, Fabio G.: Speeding up $k$-neighborhood local search in limited memory influence diagrams (2014)