Weighted Uni-Dimensional Similarities Problem with Least Absolute Value Metric Is NP-Hard.

摘要

The purpose of this paper is to prove that the weighted uni-dimensional similarities problem with least absolute value metric (USPAM) is, in general, NP-Hard. In the first four sections of the paper, the USPAM problem and four lemmas are presented which will be used in Section 6 to prove the main theorem of this paper. It is shown that the simple max cut problem can, in a polynomial number of steps, be converted into a special case of the USPAM problem, which shows that the USPAM problem is NP-Hard. Finally, some special cases of the USPAM problem are described for which polynomial solutions exist.