Qualitative Properties of k-Center Problems

2024/09/18 by Vo Si Trong Long, Nguyen Mau Nam, Long, Vo Si Trong +5 · 1 citation
Business, Management and Accounting · Engineering · #FOS: Mathematics #Facility Location and Emergency Management #Optimization and Control (math.OC) #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2409.12091

openalex publication_date 2024/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we study generalized versions of the k-center problem, which involves finding k circles of the smallest possible equal radius that cover a finite set of points in the plane. By utilizing the Minkowski gauge function, we extend this problem to generalized balls induced by various convex sets in finite dimensions, rather than limiting it to circles in the plane. First, we establish several fundamental properties of the global optimal solutions to this problem. We then introduce the notion of local optimal solutions and provide a sufficient condition for their existence. We also provide several illustrative examples to clarify the proposed problems.

Cited by

• The Existence and Stability of Generalized Multi-Source Weber Problems

Related

• Computing k-Centers On a Line
• A Constant Approximation for Colorful k-Center
• The 2-center problem and ball operators in strictly convex normed planes
• Geometric k-Center Problems with Centers Constrained to Two Lines
• The Non-Uniform k-Center Problem