Vi studerar lokala sökalgoritmer för metriska fall av anläggningslokaliseringsproblem: problemet med okapacitet anläggningslokalisering (UFL), samt icke-kondenserade versioner av k-median-, k-center- och kmeans-problemen. Alla dessa problem medger naturliga lokala sökheuristik: till exempel, i UFL-problemet naturliga rörelser är att öppna en ny anläggning, stänga en befintlig anläggning, och att byta en stängd anläggning för en öppen; i k-medianer, vi får bara byta rörelser. Den lokala sökalgoritmen för k-median analyserades av Arya et al. (SIAM J. Comput.) )............................................................................................................ 33(3):544-562, 2004 ), som använde en smart "koppling" argument för att visa att lokala optima hade kostat högst konstant gånger den globala optimal. De använde också detta argument för att visa att den lokala sökalgoritmen för UFL var 3 approximation; deras tekniker har sedan dess tillämpats på andra anläggnings lokaliseringsproblem. I detta dokument ger vi ett bevis på k-medianresultatet som undviker detta kopplingsargument. Dessa argument kan användas i andra inställningar där Arya et al. Argument har använts. Vi visar också att för problemet med att öppna k anläggningar F för att minimera den objektiva funktionen 0 p (F ) = j.V d(j, F ) p 1/p, är den naturliga swap-baserade lokala-sök algoritmen en (p)-tillnärmning. Detta innebär konstant-faktor approximationer för k-medianer (när p = 1), och k-means (när p = 2), och en O (log n)- approximation algoritm för k-center problem (som i huvudsak är p = log n).
För allmänna mätvärden visade Gupta och Tangwongsan REF att den lokala sökalgoritmen är en (25 + )-uppskattning.
Simpler Analyses of Local Search Algorithms for Facility Location
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}