The Euclidean k-Supplier Problem

• 成果类型: Article
• 署名作者: Nagarajan, Viswanath; Schieber, Baruch; Shachnai, Hadas
• 署名单位: University of Michigan System; University of Michigan; International Business Machines (IBM); IBM USA; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.20180953
• 发表日期: 2020
• 页码: 1-14
• 关键词: approximation algorithms

摘要

The k-supplier problem is a fundamental location problem that involves opening k facilities to minimize the maximum distance of any client to an open facility. We consider the k-supplier problem in Euclidean metrics (of arbitrary dimension) and present an algorithm with approximation ratio 1 + root 3 < 2.74. This improves upon the previously known 3-approximation algorithm, which also holds for general metrics. Our result is almost best possible as the Euclidean k-supplier problem is NP-hard to approximate better than a factor of root 7 > 2.64. We also present a nearly linear time algorithm for the Euclidean k-supplier in constant dimensions that achieves an approximation ratio better than three.