Solving k-center problems involving sets based on optimization techniques

Nguyen Thai An (), Nguyen Mau Nam () and Xiaolong Qin ()
Additional contact information
Nguyen Thai An: University of Electronic Science and Technology of China
Nguyen Mau Nam: Portland State University
Xiaolong Qin: Hangzhou Normal University

Journal of Global Optimization, 2020, vol. 76, issue 1, No 9, 189-209

Abstract: Abstract The continuous k-center problem aims at finding k balls with the smallest radius to cover a finite number of given points in $$\mathbb {R}^n$$Rn. In this paper, we propose and study the following generalized version of the k-center problem: Given a finite number of nonempty closed convex sets in $$\mathbb {R}^n$$Rn, find k balls with the smallest radius such that their union intersects all of the sets. Because of its nonsmoothness and nonconvexity, this problem is very challenging. Based on nonsmooth optimization techniques, we first derive some qualitative properties of the problem and then propose new algorithms to solve the problem. Numerical experiments are also provided to show the effectiveness of the proposed algorithms.

Keywords: k-center problem; Multifacility location problem; Majorization-minimization principle; Difference of convex functions; Primary: 49J52; 49J53; Secondary: 90C30 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-019-00834-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:76:y:2020:i:1:d:10.1007_s10898-019-00834-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-019-00834-6

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().