De grootste kennisbank van het HBO

Inspiratie op jouw vakgebied

Vrij toegankelijk

Terug naar zoekresultatenDeel deze publicatie

Approximability of the p-neighbor k-supplier problem

Rechten:

Approximability of the p-neighbor k-supplier problem

Rechten:

Samenvatting

We consider the dispersed -neighbor -supplier problem. In the classical -supplier problem, we have to select suppliers in a metric space such that the maximum distance between a customer and its closest supplier is minimized. Here, we generalize this problem to the case where each customer possibly needs service from more than one supplier. Moreover, the selected suppliers should not be too close to each other, i.e., they need to be dispersed. For the classical -supplier problem, and its special case the

-center problem, there is a 3- and a 2-approximation respectively. We show that these guarantees can also be given in the case when customers need service from multiple suppliers, without imposing dispersion constraints. If we generalize the problem to the dispersed case, without imposing neighboring constraints, we get inapproximability results depending on the measure of dispersion. We also show (almost) matching upper bounds. Finally, we show that adding both the neighbor requirement and the dispersion requirement leads to an inapproximable problem.


Toon meer
OrganisatieNederlandse Defensie Academie
AfdelingFaculteit Militaire Wetenschappen
LectoraatMilitair Technische Wetenschappen
Gepubliceerd inDiscrete Applied Mathematics ScienceDirect, Vol. 289, Pagina's: 219-229
Datum2021-01-31
TypeArtikel
TaalEngels

Op de HBO Kennisbank vind je publicaties van 26 hogescholen

De grootste kennisbank van het HBO

Inspiratie op jouw vakgebied

Vrij toegankelijk