Apappu writeup on Cohen et al.

From Cohen Courses
Jump to navigationJump to search

This is a review of Cohen_2000_hardening_soft_information_sources by user:Apappu.

  • This paper is about mapping soft data to hard data.
  • Given a soft database and a structure of potential interpretations highlighting candidate correference relations, then find the hard database H.
  • Authors show that this optimization problem is NP-complete hence it has to be solved approximately using a greedy algorithm.
  • Concept of chain of interpretation arcs to form a set of potential Interpretation arcs that minimize the cost function c(I)(referred in the paper).
  • A greedy algorithm has been employed to minimize the cost the function since the task of optimization of the original function is intractable.

On a side note:

  • According to (Nemhauser et al' 78, An analysis of approximations for maximizing submodular set functions - GL Nemhauser, LA Wolsey, ML Fisher - Math. Program., 1978) Greedy algorithm gives a near optimal solution about 63% times.