The Online Multicommodity Connected Facility Location Problem

摘要

Grandoni and Rothvoss introduced the Multicommodity Connected Facility Location problem, a generalization of the Connected Facility Location problem which arises from a combination of the Facility Location and the Steiner Forest problems through the rent-or-buy model. We consider the online version of this problem and present a randomized algorithm that is O(log~2 n)-competitive, where n is the number of given client pairs. Our algorithm combines the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden with previous algorithms for the Online Prize-Collecting Facility Location and the Online Steiner Forest problems. Also, for the special case of the problem with edge scale factor equals 1, we show that a variant of our algorithm is deterministic and O(log n)-competitive. Finally, we speculate on the possibility of finding a O(log n)-competitive algorithm for the general case and the difficulties to achieve such ratio.