K-CENTER AND K-MEDIAN PROBLEMS IN GRADED DISTANCES

Graded distances are generalizations of the Euclidean distance on poin ts in R-1. They have been used in the study of special cases of NP-har d problems. In this paper, we study the k-center and k-median problems with graded distance matrices. We first prove that the k-center probl em is polynomial time solvable when the distance matrix is graded up t he rows or graded down the rows. We then prove that the k-median probl em is NP-complete when the distance matrix is graded up the rows or gr aded down the rows. An easy special case of the k-median problem with graded distance matrices is also discussed. (C) 1998-Elsevier Science B.V. All rights reserved.