Pankratov, Denis
                            (Ed.)
                        
                    
            
                            In the clustering with neighborhoods problem one is given a set S of disjoint convex objects in the plane and an integer parameter k ≥ 0, and the goal is to select a set C of k center points in the plane so as to minimize the maximum distance of an object in S to its nearest center in C. Previously [HKR21] showed that this problem cannot be approximated within any factor when S is a set of disjoint line segments, however, when S is a set of disjoint disks there is a roughly 8.46 approximation algorithm and a roughly 6.99 approximation lower bound. In this paper we investigate this significant discrepancy in hardness between these shapes. Specifically, we show that when S is a set of axis aligned squares of the same size, the problem again is hard to approximate within any factor. This surprising fact shows that the discrepancy is not due to the fatness of the object class, as one might otherwise naturally suspect. 
                        more » 
                        « less   
                     An official website of the United States government
An official website of the United States government 
				
			 
					 
					
 
                                    