CSpace
K-center and K-median problems in graded distances
Lin, GH; Xue, GL
1998-10-28
Source PublicationTHEORETICAL COMPUTER SCIENCE
ISSN0304-3975
Volume207Issue:1Pages:181-192
AbstractGraded distances are generalizations of the Euclidean distance on points in R-1. They have been used in the study of special cases of NP-hard problems. In this paper, we study the k-center and k-median problems with graded distance matrices. We first prove that the k-center problem is polynomial time solvable when the distance matrix is graded up the rows or graded down the rows. We then prove that the k-median problem is NP-complete when the distance matrix is graded up the rows or graded 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.
Keywordthe k-center problem the k-median problem graded distance matrix computational complexity
Language英语
WOS Research AreaComputer Science
WOS SubjectComputer Science, Theory & Methods
WOS IDWOS:000076053700013
PublisherELSEVIER SCIENCE BV
Citation statistics
Cited Times:1[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/13356
Collection中国科学院数学与系统科学研究院
Affiliation1.Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA
2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China
Recommended Citation
GB/T 7714
Lin, GH,Xue, GL. K-center and K-median problems in graded distances[J]. THEORETICAL COMPUTER SCIENCE,1998,207(1):181-192.
APA Lin, GH,&Xue, GL.(1998).K-center and K-median problems in graded distances.THEORETICAL COMPUTER SCIENCE,207(1),181-192.
MLA Lin, GH,et al."K-center and K-median problems in graded distances".THEORETICAL COMPUTER SCIENCE 207.1(1998):181-192.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Lin, GH]'s Articles
[Xue, GL]'s Articles
Baidu academic
Similar articles in Baidu academic
[Lin, GH]'s Articles
[Xue, GL]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Lin, GH]'s Articles
[Xue, GL]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.