Apappu writeup on Cohen et al.
From Cohen Courses
Jump to navigationJump to searchThis 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.