An improved approximation algorithm for the most points covering problem

DOI10.1007/s00224-011-9353-4zbMath1253.68148OpenAlexW2036721110MaRDI QIDQ692901

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

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

Related Items (2)

AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ The most points connected-covering problem with two disks

Cites Work

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

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