Vi anser att den mobila anläggningen plats (MFL) problem. Vi får en uppsättning anläggningar och kunder belägna i ett gemensamt metriska utrymme G = (V, c). Målet är att flytta varje anläggning från sin ursprungliga plats till en destination (i V ) och tilldela varje kund till destinationen för vissa anläggningar för att minimera summan av rörelsekostnaderna för anläggningarna och kostnaderna kund-tilldelning. Detta abstracts facility-location inställningar där man har flexibiliteten att flytta anläggningar från sina nuvarande platser till andra destinationer för att tjäna kunderna mer effektivt genom att minska sina tilldelningskostnader. Vi ger den första lokala sökning baserad approximation algoritm för detta problem och uppnå den mest kända approximation garanti. Vårt huvudsakliga resultat är (3 + ) - approximation för detta problem för alla konstant > 0 med hjälp av lokal sökning. Den tidigare bästa garantin för MFL var en 8-approximationsalgoritm på grund av [13] baserad på LP-avrundning. Vår garanti matchar den mest kända approximationsgarantin för k-median-problemet. Eftersom det finns en approximation-bevarande minskning från k-median problemet till MFL, skulle varje förbättring av vårt resultat innebära en motsvarande förbättring av k-median problemet. Dessutom är vår analys stram (upp till O(1) faktorer) eftersom det tajta exemplet för den lokala sökbaserade 3- approximationsalgoritmen för k-median enkelt kan anpassas för att visa att vår lokala sökalgoritm har ett snävt approximationsförhållande på 3. En av de viktigaste nyheterna i analysen är att för att generera en lämplig samling av lokala sökande rörelser vars resulterande ojämlikhet ger den önskade bunden på kostnaden för en lokal-optimum, definierar vi en trädliknande struktur som (lösligt talat) fungerar som ett "återhämtning träd", med vilket vi leker av lokal-sök flyttar genom att utforska detta träd till ett konstant djup. Våra resultat sträcker sig till den viktade generaliseringen där i varje anläggning i har en icke-negativ vikt w i och rörelsekostnaden för i är w i gånger avståndet som transporteras av i.
En polynom (3 + ) - approximation algoritm visades i REF.
Local-Search based Approximation Algorithms for Mobile Facility Location Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}