The Euclidean k -Supplier Problem

Viswanath Nagarajan (), Baruch Schieber () and Hadas Shachnai ()
Additional contact information
Viswanath Nagarajan: Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109;
Baruch Schieber: IBM T.J. Watson Research Center, Yorktown Heights, New York 10598;
Hadas Shachnai: Computer Science Department, Technion, Haifa, Israel 3200003

Mathematics of Operations Research, 2020, vol. 45, issue 1, 1–14

Abstract: 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 + 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 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.

Keywords: approximation algorithms; facility location (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.20180953 (application/pdf)

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:inm:ormoor:v:45:y:2020:i:1:p:1-14

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().