Det kapacierade K-center problemet är en grundläggande anläggning plats problem, där vi uppmanas att lokalisera K anläggningar i en graf, och tilldela hörn till anläggningar, för att minimera det maximala avståndet från en vertex till den anläggning som den tilldelas. Dessutom kan varje anläggning tilldelas högst L hörn. Detta problem är känt för att vara NP-hård. Vi ger polynom tid approximation algoritmer för två olika versioner av detta problem som uppnår approximationsfaktorerna 5 och 6. Vi studerar också några generaliseringar av detta problem.
Den kapacierade k-center problemet har en 6- approximation REF.
The Capacitated K-Center Problem
{'venue': 'In Proceedings of the 4th Annual European Symposium on Algorithms, Lecture Notes in Computer Science 1136', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}