The Euclidean k-supplier problem

Viswanath Nagarajan, Baruch Schieber, Hadas Shachnai

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1-14
Number of pages14
JournalMathematics of Operations Research
Volume45
Issue number1
DOIs
StatePublished - Feb 1 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Approximation algorithms
  • Facility location

Fingerprint

Dive into the research topics of 'The Euclidean k-supplier problem'. Together they form a unique fingerprint.

Cite this