Vi presenterar den första approximationsalgoritmen för konstant faktor för det metriska k-medianproblemet. K-medianproblemet är ett av de mest välstuderade klusterproblemen, dvs. de problem där syftet är att dela upp en given uppsättning punkter i kluster så att punkterna i ett kluster är relativt nära med avseende på någon åtgärd. För det metriska k-medianproblemet får vi n-poäng i ett metriska utrymme. Vi väljer k av dessa att vara kluster centra, och sedan tilldela varje punkt till sin närmaste utvalda centrum. Om punkt j tilldelas ett centrum i, kostnaden uppstår är proportionell mot avståndet mellan i och j. Målet är att välja k-centra som minimerar summan av tilldelningskostnaderna. Vi ger en 6 2 3 - approximation algoritm för detta problem. Detta förbättrar på det mest tidigare kända resultatet av O(log k log k), som erhölls genom raffinering och derandomizing en randomiserad O(log n log n)-tillnärmning algoritm av Bartal.
Charikar m.fl. REF erhöll den första O(1)- approximation algoritm för k-median, genom avrundning LP avkoppling; de fick en approximationsgrad på 6 2 3.
A constant-factor approximation algorithm for the k-median problem
{'venue': 'In Proceedings of the 31st Annual ACM Symposium on Theory of Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}