Online maximum k-coverage

DOI10.1016/J.DAM.2012.04.005zbMATH Open1246.05079OpenAlexW2258427920MaRDI QIDQ442204FDOQ442204

Authors: Giorgio Ausiello, G. Lucarelli, Vangelis Th. Paschos, Nicolas Boria, A. 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

Recommendations

• Online maximum \(k\)-coverage
• Online maximum \(k\)-interval coverage problem
• Online algorithms for the maximum \(k\)-interval coverage problem
• Online and dynamic algorithms for set cover
• The Online Submodular Cover Problem
• The online set cover problem
• The online set cover problem
• Optimal semi-online algorithms for machine covering
• On-line vertex-covering
• Online primal-dual algorithms for covering and packing

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)

Cites Work

• A threshold of ln n for approximating set cover
• Approximation algorithms for maximization problems arising in graph partitioning
• Online primal-dual algorithms for covering and packing
• Some simplified NP-complete graph problems
• The online set cover problem
• The quadratic 0-1 knapsack problem with series-parallel support
• Title not available (Why is that?)
• On approximation of max-vertex-cover
• Title not available (Why is that?)
• Set covering with our eyes closed
• Greedy algorithms for on-line set-covering
• Title not available (Why is that?)

Cited In (11)

• Online variable sized covering
• Title not available (Why is that?)
• Optimal online \(k\)-min search
• A fast tri-individual memetic search approach for the distance-based critical node problem
• Better streaming algorithms for the maximum coverage problem
• Online maximum \(k\)-coverage
• On-line vertex-covering
• Online algorithms for the maximum \(k\)-interval coverage problem
• Online k-max Search Algorithms with Applications to the Secretary Problem
• Online maximum \(k\)-interval coverage problem
• Online budgeted maximum coverage

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442204)