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):

• Ritchey, Nathan P.
• Thompson, Gerald L.

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.

Descriptors:

• *WEIGHTING FUNCTIONS
• THEOREMS
• POLYNOMIALS
• CUTTING
• ONE DIMENSIONAL
• SOLUTIONS(GENERAL)

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE