I detta dokument ger vi snabbare algoritmer för att lösa det geometriska medianproblemet: givet n punkter i R d beräkna en punkt som minimerar summan av Euclidean avstånd till punkterna. Detta är ett av de äldsta icke-triviala problemen i beräkningsgeometrin men trots en lång historia av forskning de tidigare snabbaste körtiderna för att beräkna en (1 + )-ungefärlig geometrisk median var O(d · n 4/3 −8/3 ) av Chin et. al,Õ(d exp −4 log −1 ) av Badoiu et. al, O(nd+ poly(d, −1 )) av Feldman och Langberg och den polynomiska körtiden för O(nd) O(1) log 1 ) av Parrilo och Sturmfels och Xue och Ye. I detta dokument visar vi hur man beräknar en sådan ungefärlig geometrisk median i tiden O(nd log 3 n ) och O(d −2 ). Medan vår O(d −2 ) är en ganska enkel tillämpning av stokastisk subgradient nedstigning, är vår O(nd log 3 n ) tid algoritm en ny lång steg inre punkt metod. Vi börjar med en enkel O(nd) O(1) log 1 ) tid interiör punkt metod och visa hur man kan förbättra den, slutligen bygga en algoritm som är ganska icke-standard ur perspektivet för inredning punkt litteratur. Vårt resultat är ett av få fall av överträffande standard inre punktteori. Dessutom är det det enda fallet vi vet om var inre punktmetoder ger en nästan linjär tid algoritm för en kanonisk optimering problem som traditionellt kräver superlinjär tid.
Mer nyligen, Cohen et al. REF utvecklade en av de snabbaste (1 + ε) approximationsalgoritmerna hittills för det geometriska medianproblemet via stokastiska subgradientmetoder.
Geometric median in nearly linear time
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}