DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA235060
Title:
The Weighted Uni-Dimensional Similarities Problem with Least Absolute Value Metric Is NP-Hard
Descriptive Note:
Management sciences research rept.
Corporate Author:
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Report Date:
1990-04-01
Pagination or Media Count:
11.0
Abstract:
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.
Distribution Statement:
APPROVED FOR PUBLIC RELEASE