Vi ger en konstant faktor approximation algoritm för följande generalisering av k-median problemet. Vi får en uppsättning kunder och anläggningar i ett metriska utrymme. Varje anläggning har en öppningskostnad, och vi får också en budget B. Målet är att öppna en undergrupp av anläggningar av total kostnad på högst B, och minimera den totala anslutningskostnaden för kunderna. Detta löser ett öppet problem med Krishnaswamy-Kumar-Nagarajan-Sabharwal-Saha. Den naturliga linjära programmeringen avslappning för detta problem har obegränsad integrality gap. Vår algoritm stärker denna avkoppling genom att lägga till begränsningar som anger vilka faciliteter en klient kan få tilldelas. Vi visar att efter lämplig modifiering av en fraktionerad lösning, kan man få rika strukturella egenskaper som gör att vi kan få önskad approximation förhållande.
Som anges ovan beror den enda tidigare approximationsalgoritm för konstant faktor för MRoB-problemet som studeras i detta dokument på Kumar et al. Hoppa över det.
A constant-factor approximation algorithm for the multicommodity rent-or-buy problem
{'venue': 'In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}