Abstrakt. Vi anser att fel-toleranta anläggningen Placement problem (F T F P ), som är en generalisering av den klassiska okapacitet anläggning plats problem (U F L). I F T F P problem vi har en uppsättning kunder C och en uppsättning anläggningar F. Varje anläggning i  på F kan öppnas många gånger. För varje öppning av anläggningen i vi betalar fi ≥ 0. Vårt mål är att ansluta varje klient j  på C med rj ≥ 1 öppna anläggningar på ett sätt som minimerar den totala kostnaden för öppna anläggningar och etablerade anslutningar. I en serie av senaste papper F T F P var väsentligen reducerad till F T F L och sedan till U F L visar det kan approximeras med förhållandet 1.575. I detta dokument visar vi att F T F P faktiskt kan approximeras ännu bättre. Vi anser att approximationsförhållandet är en funktion av r = minj på C rj (minimikrav för en kund). Med ökande r approximation förhållandet mellan vår algoritm λr konvergerar till en. För r > 1 är värdet för λr dessutom mindre än 1.463 (fasthet för approximation av UFL). Vi visar också en lägre gräns på 1.278 för approximabiliteten av FaultTolerant Facility Location problem (F T F L) för godtycklig r. Redan för r > 3 får vi att F T F P kan approximeras med förhållandet 1.275, visar att under standard komplexitet teoretiska antaganden F T F P är strikt bättre approximabel än F T F L.
REF visade att approximationsfaktorn kan förbättras ytterligare (till en faktor som är ännu bättre än den nedre gränsen på 1.463 för det grundläggande problemet med okapacitetsanläggningens lokalisering) när den lägsta efterfrågan är större än 1, och ger en lägre gräns på 1.278.
Improved approximation algorithm for Fault-Tolerant Facility Placement
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}