Polynomial Solvability of Cost-based Abduction
Document Type
Article
Publication Date
9-1996
Abstract
In recent empirical studies we have shown that many interesting cost-based abduction problems can be solved efficiently by considering the linear program relaxation of their integer program formulation. We tie this to the concept of total unimodularity from network flow analysis, a fundamental result in polynomial solvability. From this, we can determine the polynomial solvability of abduction problems and, in addition, present a new heuristic for branch and bound in the non-polynomial cases.
Source Publication
Artificial Intelligence
Recommended Citation
Santos, E., & Santos, E. S. (1996). Polynomial solvability of cost-based abduction. Artificial Intelligence, 86(1), 157–170. https://doi.org/10.1016/0004-3702(96)00016-1
COinS
Comments
The "Link to Full Text" on this page opens or saves the article PDF hosted at the publisher website, Elsevier ScienceDirect. The record of the article is available from the DOI link.