An improved approximation algorithm for the most points covering problem

DOI10.1007/S00224-011-9353-4zbMATH Open1253.68148OpenAlexW2036721110MaRDI QIDQ692901FDOQ692901

Hossein Ghasemalizadeh, Mohammadreza Razzazi

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9353-4

zbMATH Keywords

approximation algorithmcomputational geometrygeometric coveringmost points coveringpartial covering

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• A threshold of ln n for approximating set cover
• Introduction to algorithms
• Approximation algorithms for partial covering problems
• The budgeted maximum coverage problem
• Exact and approximation algorithms for clustering
• Approximation schemes for covering and packing problems in image processing and VLSI
• Optimal packing and covering in the plane are NP-complete
• Improved approximation algorithms for geometric set cover
• Covering a set of points in multidimensional space
• On a circle placement problem
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Theory and Application of Width Bounded Geometric Separator
• Covering many or few points with unit disks

Cited In (3)

• The most points connected-covering problem with two disks
• Title not available (Why is that?)
• An algorithmic framework for solving geometric covering problems -- with applications

This page was built for publication: An improved approximation algorithm for the most points covering problem

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