ON THE LOWER BOUND OF THE COMPETITIVE RATIO FOR THE WEIGHTED ONLINE ROOMMATES PROBLEM
Satyajit Banerjee · Discrete Mathematics Algorithms and Applications · 2010
We show that the best possible worst case competitive ratio of any deterministic algorithm for weighted online roommates problem is arbitrarily close to 4. This proves that the 4-competitive algorithm proposed by Bernstein and Rajagopalan [3] for the weighted version of the online roommates problem actually attains the best possible competitive ratio.