I detta dokument presenteras utformning och analys av parallella approximationsalgoritmer för anläggningslokaliseringsproblem, inklusive NC- och RNC-algoritmer för (metrisk) anläggningsplats, k-center, k-median och k-medel. Dessa problem har fått stor uppmärksamhet under de senaste årtiondena från approximationsalgoritmen, som främst är inriktad på att förbättra approximationsgarantierna. I denna tidning frågar vi: Är det möjligt att parallellisera några av de vackra resultaten från den sekventiella inställningen? Vår utgångspunkt är en liten, men varierad, undergrupp av resultat i approximationsalgoritmer för anläggning-lokalisering problem, med ett primärt mål att utveckla tekniker för att utforma sina effektiva parallella motsvarigheter. Vi fokuserar på att ge algoritmer med lågt djup, nära arbetseffektivitet (jämfört med sekventiella versioner) och låg cache komplexitet.
Blelloch och Tangwongsan REF föreslår en parallell approximeringsalgoritm för anläggningens placering i PRAM-modellen.
Parallel approximation algorithms for facility-location problems
{'venue': "SPAA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}