An improved approximation algorithm for the most points covering problem
DOI10.1007/S00224-011-9353-4zbMATH Open1253.68148OpenAlexW2036721110MaRDI QIDQ692901FDOQ692901
Authors: 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
Recommendations
- Polynomial time approximation schemes for minimum disk cover problems
- An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
- Unit disk cover problem in 2D
- A constant-factor approximation for multi-covering with disks
- A constant-factor approximation for multi-covering with disks
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)
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)
