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
Personal Author(s):
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.
Subject Categories:
- Numerical Mathematics