2018/09/23 by Sharareh Alipour, Alipour, Sharareh
Computer Science · Decision Sciences · Mathematics · #Advanced Statistical Methods and Models #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Fuzzy Systems and Optimization #Multi-Criteria Decision Making #cs.CG
paper · pdf · doi:10.48550/arxiv.1809.08549
some parts are wrong and need major revision
openalex publication_date 2018/09/23 · openalex created_date 2018/09/27 · arxiv created 2020/06/11 · arxiv updated 2020/06/12 · openalex updated_date 2026/07/28
In real applications, database systems should be able to manage and process data with uncertainty. Any real dataset may have missing or rounded values, also the values of data may change by time. So, it becomes important to handle these uncertain data. An important problem in database technology is to cluster these uncertain data. In this paper, we study the k-center problem for uncertain points in a general metric space. First we present a greedy approximation algorithm that builds k centers using a farthest-first traversal in k iterations. This algorithm improves the approximation factor of the unrestricted assigned k-center problem from 10 to 6. Next we restrict the centers to be selected from a finite set of points and we show that the optimal solution for this restricted setting is a 2-approximation factor solution for the optimal solution of the assigned k-center problem. Using this idea we improve the approximation factor of the unrestricted assigned k-center problem to 4 by increasing the running time mildly.