Polynomial Solvability of Cost-Based Abduction

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1996
Accession Number
ADA531047

Entities

People

  • Eugene S. Santos
  • Eugene Santos

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Artificial Intelligence
  • Computer Programming
  • Construction
  • Electronic Mail
  • Engineering
  • Guarantees
  • Inequalities
  • Integer Programming
  • Integrals
  • Linear Programming
  • Optimization
  • Polynomials
  • Probability
  • Reasoning
  • Simplex Method

Fields of Study

  • Computer science

Readers

  • International Relations and Conflict Resolution
  • Operations Research