Before revision:  Although the denoised problem turns out to be NP-hard, we give a linear-programming based approximation algorithm for it.
After revision:  Although this denoised problem turns out to be NP-hard, we give a linear-programming based approximation algorithm for it.