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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1990
Accession Number
ADA235060

Entities

People

  • Gerald L. Thompson
  • Nathan P. Ritchey

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Computer Science
  • Contracts
  • Integer Programming
  • Integrals
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Military Research
  • Operations Research
  • Polynomials
  • Systems Science
  • Universities

Fields of Study

  • Mathematics

Readers

  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.
  • Nanofabrication and Microfabrication.