Online maximum k-coverage

DOI10.1016/J.DAM.2012.04.005MaRDI QIDQ442204zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1256771 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Approximation algorithms for maximization problems arising in graph partitioning
• Greedy algorithms for on-line set-covering
• On approximation of max-vertex-cover
• Online primal-dual algorithms for covering and packing
• Set covering with our eyes closed
• Some simplified NP-complete graph problems
• The online set cover problem
• The quadratic 0-1 knapsack problem with series-parallel support

Cited in

(11)

• Online variable sized covering
• scientific article; zbMATH DE number 1953086 (Why is no real title available?)
• Optimal online \(k\)-min search
• Better streaming algorithms for the maximum coverage problem
• A fast tri-individual memetic search approach for the distance-based critical node 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)