## 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 language | English (US) |
---|---|

Pages (from-to) | 1-14 |

Number of pages | 14 |

Journal | Mathematics of Operations Research |

Volume | 45 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1 2020 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Mathematics
- Computer Science Applications
- Management Science and Operations Research

## Keywords

- Approximation algorithms
- Facility location