The Weighted Uni-Dimensional Similarities Problem with Least Absolute Value Metric Is NP-Hard
Management sciences research rept.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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.
- Numerical Mathematics