9 citations · 9 across the 2 of their papers we have counts for
2 papers
cs.DS2013★ 9 cited
Approximating Semi-Matchings in Streaming and in Two-Party Communication
Christian Konrad, Adi Rosén
We study the communication complexity and streaming complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E), with n = |A|, is a su…
cs.DS2009
On the Additive Constant of the k-server Work Function Algorithm
Yuval Emek, Pierre Fraigniaud, Amos Korman +1
We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a cons…