Abstract: The clustering problem is a well-studied problem in computer science. Given a set of points in metric space, the objective of the clustering problem is to partition the data points into clusters such that the distances between points within the same cluster are small and the distance between points in different cluster are large. As an unsupervised learning procedure, a number of variants of clustering problem have been investigated and many important approaches have been proposed. Among these variants, the Euclidean k-center problem and Euclidean k-median problem have received considerable attentions [2; 4; 10; 11; 13; 34; 36; 40; 81] from the fields of computational geometry and combinatorial optimizations. Such problems are NP-hard, and have been studied from the perspective of worst case performance guarantees. The approaches to design approximation algorithms can be roughly classified into three categories [75], LP rounding techniques [27; 76], local search heuristics [8; 17], and primal dual method [57]. We will present results for the clustering and related problems by exploring various techniques. First, we study the clustering problem with prescribed grouping information in this thesis. In such clustering problem, some pre-existing partial grouping information, which requires that some points must belong to the same cluster, has to be preserved by the clustering algorithm. In particular, we consider the interesting generalizations of the Euclidean k-center and k-median problems called k-center problem with prescribed grouping information (denoted as KCWPGI) and k-median problem with prescribed grouping information (denoted as KMWPGI) respectively in d-dimensional Euclidean space Rd. Our results about clustering problem with prescribed grouping information can be summarized as follows: (1) an O( m + n log k)-time 3-approximation algorithm for the KCWPGI problem; (2) an O( km)-time (1 + $3$)-approximation algorithm for the KCWPGI problem; (3) an O(dm/ε + 2O (k log k/ε)dn + (1/ε)5n)-time (2 + ε)-approximation algorithm for the KCWPGI; (4) a (3 + ε)-approximation algorithm for KMWPGI problem. Next, we study clustering problem on bipartite graph formed by a set of facility locations and client locations, which is also called facility location problem. The clients location served by the same facility belongs to the same cluster. Instead of specifying the number of clusters, we seeks to open facilities so as to minimize the sum of cost of building facilities and connecting clients to opened facilities. Such clustering problem is also called facility location problem. (Abstract shortened by UMI.)