Vi får en 1,5-approximation algoritm för den metriska okapacitet anläggning plats problem (UFL), som förbättrar på den tidigare mest kända 1.52- approximation algoritm av Mahdian, Ye och Zhang. Observera, att den approximabilitet lägre bundet av Guha och Khuller är 1.463.. En algoritm är en (λ f,λ c ) - approximation algoritm om lösningen den producerar har total kostnad som mest λ f · F * + λ c · C *, där F * och C * är anläggningen och anslutningskostnaden för en optimal lösning. Vår nya algoritm, som är en modifiering av (1 + 2/e)-tillnärmningsalgoritmen för Chudak och Shmoys, är en (1.6774,1.3738)-tillnärmningsalgoritm för UFL-problemet och är den första som berör den ungefärliga gränskurvan (γ f, 1 + 2e −γ f ) upprättad av Jain, Mahdian och Saberi. Som en följd av detta får vi den första optimala approximationsalgoritmen för fall som domineras av anslutningskostnader. I kombination med en (1.11.1.7764)-tillnärmningsalgoritm som föreslås av Jain et al., och senare analyseras av Mahdian et al., får vi den övergripande approximeringsgarantin på 1,5 för det metriska UFL-problemet. Vi beskriver också hur vi använder vår algoritm för att förbättra approximationsförhållandet för 3-nivåversionen av UFL.
Byrka och Aardal REF förbättrade sedan approximationsförhållandet för k = 3 till 2.492.
An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}