I k-center problemet, med tanke på ett metriska utrymme V och ett positivt heltal k, vill man välja k element (centra) av V och ett uppdrag från V till centra, minimera det maximala avståndet mellan ett element av V och dess tilldelade centrum. En av de mest allmänna varianterna är kapaciated α-fel-tolerant k-center, där centra har en gräns för antalet tilldelade element, och, om några α-centra misslyckas, det finns en omfördelning från V till icke-feliga centra. I detta dokument presenterar vi ett nytt tillvägagångssätt för att ta itu med feltolerans, genom att välja och föröppna en uppsättning backup center, sedan lösa den erhållna kvarvarande instansen. För fallet {0, L}, ger vi approximationer med faktor 6 för det grundläggande problemet, och 7 för den så kallade konservativa varianten, när endast kunder vars centra misslyckades får omplaceras. Våra algoritmer förbättras på de mest kända faktorerna 9 respektive 17. Dessutom anser vi att det är fallet med allmän kapacitet. Förutsatt att α är konstant leder vår metod till de första approximationerna för detta fall. Vi tar också fram approximationer för det kapacierade feltoleranta k-leverantörsproblemet.
Nyligen gav REF också konstanta approximationer för k-centerkluster med feltolerans.
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}