Online Maximum k-Coverage
Paschos, Vangelis; Lucarelli, Giorgio; Giannakos, Aristotelis; Boria, Nicolas; Ausiello, Giorgio (2011), Online Maximum k-Coverage, in Arne Telle, Jan; Steffen, Martin; Owe, Olaf, Fundamentals of Computation Theory 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Proceedings, Springer : Berlin, p. 181-192
TypeCommunication / Conférence
Conference titleFundamentals of Computation Theory, FCT 2011
Book titleFundamentals of Computation Theory 18th International Symposium, FCT 2011, Oslo, Norway, August 22-25, 2011. Proceedings
Book authorArne Telle, Jan; Steffen, Martin; Owe, Olaf
Series titleLecture Notes in Computer Science
Number of pages373
MetadataShow full item record
Abstract (EN)We study an online model for the maximum k-vertex-coverage problem, where given a graph G = (V,E) and an integer k, we ask for a subset A ⊆ V, such that |A| = k and the number of edges covered by A is maximized. In our model, at each step i, a new vertex v i is revealed, and we have to decide whether we will keep it or discard it. At any time of the process, only k vertices can be kept in memory; if at some point the current solution already contains k 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 revealed is definitely deleted). We propose algorithms for several natural classes of graphs (mainly regular and bipartite), improving on an easy 21-competitive ratio. We next settle a set-version of the problem, called maximum k-(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 k.
Subjects / Keywordsbipartite graphs; vertex cover
Showing items related by title and author.