On Constraint Clustering to Minimize the Sum of Radii
Rajkumar Jain1, Narendra S. Chaudhari2
1Rajkumar Jain, Department of Computer Science & Engineering, Indian Institute of Technology, Indore (M.P), India.
2Narendra S. Chaudhari, Department of Computer Science & Engineering, Indian Institute of Technology, Indore (M.P), India.
Manuscript received on 13 August 2016 | Revised Manuscript received on 20 August 2016 | Manuscript Published on 30 August 2016 | PP: 236-239 | Volume-5 Issue-6, August 2016 | Retrieval Number: F4727085616/16©BEIESP
Open Access | Editorial and Publishing Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: We consider the min-cost k-cover problem: For a given a set P of n points in the plane, objective is to cover the n points by k disks, such that sum of the radii of the disks is minimized. In this paper we introduce the concept of constraints for min-cost k-cover problem. In any instance I of k-cover, the optimal solution value is at most the maximum radius r of ball 𝑩(𝒗 , 𝒓) centered at 𝒗 ∈ 𝑽 in I. It implies that, in optimal solutions there always exists a constraint that separates the optimal solution. Investigation formulate that a can-not link constraint always separate the optimal solution very clearly and reduces cardinality of distinct maximal discs. Introduction of constraints improves the performance of min-cost k-cover algorithm over the existing algorithms.
Keywords: K-Clustering, Min-Cost K-Cover, Minimum Sum of Radii Cover, Constraint Clustering.
Scope of the Article: Clustering