Online maximum \(k\)-coverage

DOI10.1016/j.dam.2012.04.005zbMath1246.05079OpenAlexW2258427920MaRDI QIDQ442204

Giorgio Ausiello, Vangelis Th. Paschos, Giorgio Lucarelli, Nicolas Boria, Aristotelis Giannakos

Publication date: 10 August 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.04.005

zbMATH Keywords

competitive ratiomaximum \(k\)-coveragenegative results

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (5)

A fast tri-individual memetic search approach for the distance-based critical node problem ⋮ Online budgeted maximum coverage ⋮ Online Maximum k-Coverage ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Online algorithms for the maximum \(k\)-interval coverage problem

Cites Work

• Some simplified NP-complete graph problems
• On approximation of max-vertex-cover
• The quadratic 0-1 knapsack problem with series-parallel support
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Set Covering with Our Eyes Closed
• A threshold of ln n for approximating set cover
• Online Primal-Dual Algorithms for Covering and Packing
• The Online Set Cover Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Online maximum \(k\)-coverage