Apappu writeup on Cohen et al.

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.