Online maximum kk-coverage

We study an online model for the maximum kk-vertex-coverage problem, in which, given a graph G=(V,E)G=(V,E) and an integer kk, we seek a subset A⊆VA⊆V such that |A|=k|A|=k and the number of edges covered by AA is maximized. In our model, at each step ii, a new vertex vivi is released, and we have to decide whether we will keep it or discard it. At any time of the process, only kk vertices can be kept in memory; if at some point the current solution already contains kk vertices, any inclusion of a new vertex in the solution must entail the definite deletion of another vertex of the current solution (a vertex not kept when released is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy 12-competitive ratio. We next settle a set version of the problem, called the maximum kk-(set)-coverage problem. For this problem, we present an algorithm that improves upon former results for the same model for small and moderate values of kk.