Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-319-11433-0_22 | PROBABILISTIC GRAPHICAL MODELS |
DocType | Volume | ISSN |
Conference | 8754 | 0302-9743 |
Citations | PageRank | References |
1 | 0.35 | 16 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Denis Deratani Mauá | 1 | 1 | 0.35 |
Fábio Cozman | 2 | 18 | 10.16 |