K-center and K-median problems in graded distances

DOI10.1016/S0304-3975(98)00063-2zbMath0912.68044MaRDI QIDQ1274996

Guoliang Xue, Guo-Hui Lin

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Computational complexity\(k\)-center problem\(k\)-median problemGraded distance matrix

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The quadratic minimum spanning tree problem and its variations

Uses Software

• SITATION
• MOD-DIST
• MENU-OKF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for geometric median problems
• Parallel concepts in graph theory
• The computational complexity of Steiner tree problems in graded matrices
• On the Complexity of Some Common Geometric Location Problems
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• A Best Possible Heuristic for the k-Center Problem
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• P-Complete Approximation Problems
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem