The computational complexity and approximability of a series of geometric covering problems
DOI10.1134/S008154381309006XzbMATH Open1317.68075OpenAlexW2105177507MaRDI QIDQ483201FDOQ483201
Authors: M. I. Poberii, M. Yu. Khachaĭ 
Publication date: 16 December 2014
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s008154381309006x
NP-complete problempolynomial-time approximation scheme (PTAS)\(L\)-reductionMAX-SNP-hard problempolynomial-time reduction
Analysis of algorithms and problem complexity (68Q25) 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
- Approximation algorithms for combinatorial problems
- Optimization, approximation, and complexity classes
- On the ratio of optimal integral and fractional covers
- Fast multiplication of large numbers
- Exact and approximation algorithms for clustering
- Covering things with things
- On the complexity of locating linear facilities in the plane
- Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules
Cited In (8)
- The complexity of the covering radius problem
- Title not available (Why is that?)
- Covering a simplex by spheres: complexity and algorithms
- Title not available (Why is that?)
- Parameterized complexity of geometric covering problems having conflicts
- On the approximability of covering points by lines and related problems
- Angle covers: algorithms and complexity
- Title not available (Why is that?)
This page was built for publication: The computational complexity and approximability of a series of geometric covering problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483201)
