Abstrakt. I ett program för Content Distribution Network har vi en uppsättning servrar och en uppsättning kunder som ska anslutas till servrarna. Ofta finns det några servertyper och en hård budget begränsning på antalet utplacerade servrar av varje typ. Det enklaste målet här är att distribuera en uppsättning servrar som omfattas av dessa budgetbegränsningar för att minimera summan av klientanslutningskostnader. Dessa anslutningskostnader uppfyller ofta metriska krav, eftersom de vanligtvis står i proportion till avståndet mellan en klient och en server inom ett enda autonomt system. Ett specialfall av problemet där det bara finns en servertyp är det välstuderade k-medianproblemet. I detta dokument anser vi att problemet med två servertyper, som kallas det budgeterade rödblå medianproblemet, är intressant i sig. Vi visar, något överraskande, att köra en enda swap lokal sökning för varje servertyp samtidigt, ger en konstant faktor approximation för detta fall. Dess analys är dock ganska icke-trivial jämfört med den av k-median problem (Arya et al., 2004; Gupta och Tangwongsan, 2008 ). Senare visar vi att samma algoritm ger en konstant approximation för den prissamlande versionen av det budgeterade rödblå medianproblemet där varje kund potentiellt kan betjänas med en alternativ kostnad via en annan leverantör. I processen förbättrar vi också approximationsfaktorn för det prissamlande k-medianproblemet från 4 (Charikar et al., 2001) till 3 +, som motsvarar den nuvarande bästa approximationsfaktorn för k-medianproblemet.
Hajiaghayi m.fl. REF introducerade det röd-blå medianproblemet som generaliserar k-median, och presenterade en konstant faktor approximation baserat på lokal sökning.
Budgeted Red-Blue Median and its Generalizations
{'venue': 'ESA', 'journal': None, 'mag_field_of_study': ['Computer Science']}